SSH supports certificates (and they aren't X.509 certificates; they're simple and purpose-built for SSH) which resolves the MITM problem in both directions. It's what organizations who manage large numbers of servers use already (in particular, certificates make it easy to tie logins to SSO systems, and to keep people from holding on to long-lived SSH keys). They're great, and you should check them out.

The very last thing in the world you should do is adopt something like SSHFP, a clangorous hack that ties your SSH service to a root of trust operated by a state actor.