Comment by spindritf

You can also publish fingerprints of your host key in DNS[1]. And then

    ssh -o "VerifyHostKeyDNS ask" host.example.com

Alternatively, put

    VerifyHostKeyDNS ask 

in your ssh config. Obviously, this would work better with much maligned here DNSSEC.

[1] http://tools.ietf.org/html/rfc4255