Comment by jcalvinowens

You can also address TOFU to some extent using SSHFP DNS records.

Openssh supports checking the DNSSEC signature in the client, in theory, but it's a configure option and I'm not sure if distros build with it.