Whenever you update your SSH host keys, your machine becomes compromised, or you re-install your system, the SSH host key will change. To check if there is really a man in the middle attack, it is nice to be able to print out the fingerprint of the SSH host key on the host itself. So locally log onto your machine, and do the following:
$ ssh-keygen -l -f /etc/ssh/ssh_host_rsa_key.pub
If you are using the DSA key, you should replace rsa with dsa, naturally.