This actually seems like the right use-case for SSHFP records. They allow for storing the SSH key fingerprint in a DNSSEC secured zone.
Normally this is considered rather weak, because of the reliance on DNSSEC. However, in this case I think its a very easy to take step that'll be miles better than just trusting everything.
The stronger alternative is Certificate-based SSH, but that is a lot of hassle. As it requires setting up a CA, handling revocation, and actually distributing the certificates.
At AWS this meant we had to hop to a different gateway for each region, and then onto the (stateless) production host which was recreated from scratch on every deployment... There's no way a human was going to keep all those keys straight, and everyone just disabled SSH host verification.