There is a patch here that uses GSSAPI to verify the authenticity of the server: http://www.sxw.org.uk/computing/patches/openssh.html In practice that means you don't have to bother with SSH host keys if you are running a fully Kerberised environment. The ssh server will prove it is trustworthy based on Kerberos tickets instead. The server also has to support this of course, but at least Red Hat carries this in their distributions.
We should look at the patches Red Hat carries as they seem to have done a few bug fixes.
The referenced patch also helps out with Kerberos in two ways: - It adds an option to do reverse lookup on the servers ip address to figure out the principal. - If the new GSSAPI key exchange is used, it includes the principal. So there is no guessing involved at all.
