An SSH Host Key is a public/private cryptographic key pair. The private key is kept on the server and is only readable by the sshd server process. The public key is freely available. If an SSH client has the public key for a a server, it can verify the identity of the server by successfully decoding a known message that has been encrypted with the server's private key.
When you connect to a machine using SSH for the first time, you will see a message like:
The authenticity of host 'foo (146.186.130.211)' can't be established. RSA key fingerprint is d2:3c:67:48:cb:97:51:db:a4:02:b3:3e:26:0a:b7:ac. Are you sure you want to continue connecting (yes/no)?
If you answer "yes", then the hosts public key will be stored by your client. Typical behavior under Solaris, Linux, and OS X is to store the public key in a file named:
~/.ssh/known_hosts
This is just a text file with lines that look like:
lie ssh-rsa AAAAB3NzaD1yc2EAAAABIsAAAIEB8DfSFLfl[ ...lots more stuff]
The above line contains three space separated fields. The first is the host name. The second is the name of the cryptographic algorithim associated with the public key, and the third is the public key.
Clients typically aren't very smart. If you connect to the same machine using three different names on the command line (for example, lie, lie.math.psu.edu, and 146.186.134.201), a typical client will add entries for all three.
When a host is upgraded (or re-imaged), its host key will change. The next time that you connect to that host using an SSH client, your client will complain that the host key has changed.
If you were not expecting the machine that you are connecting to to be upgraded, it is reasonable to worry that someone might have setup a host to pretend to be the host that you are connecting to. In this case, you can email help and ask if the machine has been upgraded. You can also try connecting to a different host while you wait for a response from help.
If you are reasonably sure that the host that you want to connect to has merely been upgraded and that it is unlikely that some malicious computer is masquerading as it, you can remove the old key from your client's cache.
If you are using a variant of the OpenSSH client (Solairs, Linux, OS X), you can just edit the file:
~/.ssh/known_hosts
on the client machine. That is, on the machine that you are connecting from.
Simply remove all lines containing the name or IP address of the machine that you wish to connect to using a text editor. Please do not edit this file using a word processor. Your SSH client expects your known_hosts file to have a specific format. Any word processor mark-up will confuse it.
An SSH application can store keys anywhere. There is no way of knowing without looking at the documentation for the application. If you do not know where to look for your application, send email to help. We may be able to help.
MacSFTP stores a host keys in ~/Library/Preferences/OpenSSH/known_hosts in the same format as openssl.
If you find editing your known_hosts file to be an annoying task, you're not alone. You might wonder why do SSH clients maintain this information. You can find the answer to this question and related questions by on the page: Security Focus: SSH Host Key Protection.