@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@       WARNING: POSSIBLE DNS SPOOFING DETECTED!          @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
The RSA host key for odoko.co.uk has changed,
and the key for the corresponding IP address xx.xx.xx.xx
is unchanged. This could either mean that
DNS SPOOFING is happening or the IP address for the host
and its host key have changed at the same time.
Offending key for IP in /home/xxxxxx/.ssh/known_hosts:400
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx.
Please contact your system administrator.
Add correct host key in /home/xxxxxx/.ssh/known_hosts to get rid of this message.
Offending key in /home/xxxxxx/.ssh/known_hosts:401
RSA host key for example.com has changed and you have requested strict checking.
Host key verification failed.

Have you ever got annoyed by these messages when creating new VMs? Of course, you know it has changed - you destroyed the old one and created a new one. You can use StrictHostKeyChecking, but that doesn't get rid of these messages if you get an IP that you've seen before.

My first version of this post was very clever (use ssh-keygen to identify the host, then sed, grep, etc), but reading more on another blog post I saw how easy it is:

ssh-keygen -R $HOST

This'll remove that host from your known hosts. Now, with StrictHostKeyChecking=no (at best just for your first login) you'll be able to gain access without this annoying error.