At some point, you've probably seen this message when you try to log in to one of your servers:
This is really common when you have Amazon EC2 instances behind Elastic IPs because the IP address stays the same (and probably the hostname, too), but as new instances replace old instances, the new instances' ssh keys are probably different.
But if you look carefully, you'll see that the failure message tells you how to resolve this problem:
Offending RSA key in /Users/[username]/.ssh/known_hosts:5
That means that line no. 5 of the known_hosts file contains the problematic key. So, assuming that you are sure this is NOT in fact a security breach, you can remove that line.
It's a bit of a pain-in-the-butt to manually edit this file, though. You can use sed to do it easily, but if you're like me and you don't use sed all the time, you need to look at the man pages every time you want to use it. That's why I wrote this quick bash script to do it automatically.
Drop that in your PATH and make it executable. Then you can simply type ssh-purge-host 5 to remove line 5 from your known_hosts file.
Hope that's useful!