Host keys are used to security log into remote servers (such as Virtual Private Servers – VPS). With Ubuntu if you are using host keys to sign into servers securely and have asked for strict checking, if you make a change (such as rebuilding your VPS) the host key will change and you cannot login and will get a message like:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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
…
Please contact your system administrator.
…
RSA host key for 128.0.0.128 has changed and you have requested strict checking.
Host key verification failed.

if that happens you need to remove your local host key. Then you can sign back in and you will be able to save a new copy of the host key. If you don’t know why the key has changed you should figure that out first as it maybe be an indication of an important security problem. To remove you local key, you can use ssh-keygen -R [ip address of server with the bad key] for example: ssh-keygen -R 128.0.0.128

Then when you try to sign in you will get

The authenticity of host '128.0.0.128 (128.0.0.128)' can't be established.

RSA key fingerprint is ed:...:ea.
Are you sure you want to continue connecting (yes/no)?

And if you know why (such as you made changes to the server) you can say yes and connect and save the new known host key.