Maybe I'm missing something but SSH already has a built-in solution for this, key-certs. Just sign the server key with a private CA key you trust.
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.
But wait, there's more: SSH config, resolv.conf, DNS RR setup.
A lomg checklist for successful SSHFP deployment:
So even without DNSSec using the SSHFP records is an improvement over not using them because some of the time it tells you for certain you're being interfered with.
There is no situation in which an insecure DNS response is auto-trusted by the SSH client.
You can use software like Headscale/Tailscale/Netbird on top.
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.