Or you know SSHFP records + DNSSEC to verify hostkeys.

Which is something OpenSSH already supports.