SSHFP requires you to DNSSEC-sign your zones, which virtually nobody in the technology industry does, for a variety of reasons, some involving security.
A more straightforward solution that doesn't require you to hitch your wagon to a moribund infrastructure overhaul is to use SSH certificates. SSH certificate infrastructures have other benefits beyond resolving the introduction problem; for instance, they're easier to manage than keys once set up, and, perhaps most importantly, they make it possible to issue short-lifespan keys based on single signon, which is much safer than having everyone register a canonical personal key.
There is a solution though, SSHFP records for the host. I just set them up after catching that issue just because of how frustrating blindly trusting on first use is. Now I can SSH to my servers even without anything for them being in known_hosts and it checks for SSHFP records and verifies the fingerprint and DNSSEC protects the SSHFP records.