I've wondered about SSH md5 fingerprints. When I SSH somewhere new I get this:

The authenticity of host '192.168.0.123' can't be established.
RSA key fingerprint in md5 is: 59:94:5a:d7:2b:1f:ad:6e:ef:24:4c:71:1d:3c:3b:4a
Are you sure you want to continue connecting(yes/no)?yes
Warning: Permanently added '192.168.0.123' (RSA) to the list of known hosts.

Now I understand that the idea with the md5 fingerprint is that if I know the correct md5 fingerprint on the other side I can know if I'm getting a man-in-the-middle attack. The thing is. There are cases in which I could easily verify that md5 fingerprint except I don't have the slightest idea how to do it. Does anyone know how to check it? If so, why doesn't SSH include breif insturctions in the above warning?

Even the security-minded folks I know just say “assume you arent' getting attacked on your first connection and then you get security from then on.”