Older versions of SSH kept a ~/.ssh/known_hosts file which contained the name of each server you had connected to, along with it's public key. If you ever wanted to erase a public key, you simply edited the file with your favorite text editor, found the name of the server, and then deleted that line. (You might do this for example if the server admin had changed the public key of the server, and you wanted to tell SSH that it was ok to grab the new key and use it instead of the old key.)

 New versions of SSH store the server name in a hashed form, so you can't visually identify it (it's not human readable). This is a security feature so that somebody with access to you known_hosts file can't figure out what other machines you have connected to (and that they should try to hack next, etc). But it makes your job harder when you want to delete a single host's key.

The inelegant solution is to just delete the whole file and then accept new keys from everybody, but this is a security risk. To find out which hashed entry matches the server whose key you are trying to replace, simply run the following command:

ssh-keygen -F servername.com
 

Or, even better, to simply remove the server from your known_hosts file all in one command, use:

ssh-keygen -R servername.com