It would be great if paramiko supported rfc4255, and was able to (optionally) verify host key fingerprints using SSHFP DNS records.
Bug watches keep track of this bug in other bug trackers.