If the DNS record for the host has an SSHFP (SSH FingerPrint) record, SSH will compare it to the retrieved public key(s) and refuse the connection if there is a mismatch. It can be configured to require DNSSec for this, or to only reject if it gets a secure rejection (to prevent DoS).
It works perfectly, has no notable down sides (just add a DNS record when you generate the host's SSH key), and has been around for many years.
Just means an attacker also needs to mitm DNS if you MITM the host. Not trivial, but depending on setup might not be harder.
If set to `yes`, you get automatic trust-on-first-use (no user prompt) if you use DNSSec, and you get the current asking-the-user behavior if your DNSSec is broken or you are under attack.
Obviously it's more secure if you use DNSSec, because that way you can reflexively deny any request to manually verify a host key, but it provides value regardless.
You usually need some form of trusted communication with a new server until you can give it its real identity, in the form of host names and cryptographic keys. In an enterprise environment this can usually be done with some sort of isolated management or provisioning vlan. In a cloud environment, I've seen all sorts of more or less hacky solutions but since it depends a lot on specific details of your networks and APIs, bespoke solutions are fine.