When doing dev work on EC2, I find myself destroying and creating new EC2 instances many times in a day, and I find myself hitting the "Host key verification failed" message from SSH a bit.
You could turn off the check with -o "StrictHostKeyChecking no" on the command line or in your ~/.ssh/config file, but the warning ssh gives is a good one and not one you really want to turn off. My approach has been to edit the ~/.ssh/known_hosts file and remove the old key. SSH is nice enough to tell you the exact line number. It's inelegant, but it's what I've done for years.
What I didn't realize is that ssh has a better solution.
ssh-keygen -R will update the known_hosts file, removing the old key. The next connection will prompt you to verify and add the new key. Much nicer.