OpenSSH v6.9 is very, very, very old. Latest is OpenSSH v9.0. I took a look at dns.c of the V_6_9 branch of OpenSSH repository. The key thing to note in your debug output is:

found 2 insecure fingerprints in DNS

Means that DNSSEC lookup of host.domain.tld is not a valid DNS record (totally insecured), despite generally having found two(2) distinct SSHFP resource records (secured or not).

This also means that devl host.domain.tld. would not put out in the first line the expected message of:

$ delv host.domain.tld.
; fully validated
...

While the scope of DNSSEC troubleshooting is vast and wide, a solution is not easily had within this post.

I suggest that you plug in your domain.tld into one of the two excellent online DNSSEC troubleshooters and go from there:

• https://dnsviz.net/
• https://dnssec-debugger.verisignlabs.com/

Of course, as a last resort, there is [dnssec] tag on ServerFault (yet another StackExchange group) and your fav. search engine, but it is quicker to tap an in-house DNSSEC expert for your needs.

Security Consideration

Of course, you do do have DNSSEC up and running?

Protection of SSHFP is only assured by a properly signed resource record by DNSSEC but, But ... BUT most people (and many ISPs) do not instruct their DNS resolver to only return back a valid DNS record as determined by DNSSEC; having mentioned that, the possibility of SSHFP being hijacked remains.

The problem here is not the confidentiality of the public key (it isn’t confidential).

The problem we have is the integrity of that DNS record holding this public key. While the SSHFP key data is correct in your problem statement, the bug is more of “lack of clarity” yet the logic remains defensively correct.

That is the end for this Original Question post. But I shall outline even some more security caveats.

More Caveats

If not distributed securely (via DNSSEC), such SSHFP DNS records can quite easily be tampered with or replaced with another key. So, DNSSEC must be 'enforced' before even trusting and using SSHFP.

If a faked SSH CA server has the wrong public key configured (whose private key is in the hands of someone else), the client ends up by trusting that someone else.

Caution: Improper use of SSHFP records can have serious security consequences; follow these rules to avoid creating security vulnerabilities:

• Do not create SSHFP records in a zone that is not DNSSEC-secured.
• Never configure SSH clients to use SSHFP for a domain that is not DNSSEC-secured.
• Never configure SSH clients to use VerifyHostKeysDNS yes unless the current resolver(s) properly validate DNSSEC-approved queries or use a valid DNSSEC-capable resolver list that I made using a simple delv domain.tld. command as a test for its DNSSEC-capability.
• DO ensure that all DNS resolvers directly used by your SSH clients have "accessible DNSSEC"; this means testing your roving laptop at every ISP to get that ; fully validated check.
• MOST IMPORTANTLY, always, always perform delv ssh.domain.tld. and check that first line for ; fully validated output or make DNSSEC mandatory via /etc/resolv.conf (more of this later).

Not following these rules could allow adversaries to create spoofed-SSHFP records for their SSH server(s) to impersonate yours, making SSH connections to the servers insecure and vulnerable to attacks.

You can avoid the "always perform delv ssh.domain.tld for ; fully validated) by having your host's glibc library perform this at resolve time (via resolver(3) but NOT the gethostbyname(3) function call). If you must require absolute DNSSEC-verified DNS queries for all your DNS needs, you could insert the following into your /etc/resolv.conf (only if you have glibc v2.38 or later):

File: /etc/resolv.conf

.
.
.
options edns0
options trust-ad
options ndots:2
.
.
.
search domain.tld
nameserver 192.168.1.1

Once this gets DNSSEC-secured, there are a couple of steps required to troubleshoot the mechanism of SSHFP DNS record and SSH clients.

Validating SSHFP Setup

The seven(7) steps are listed in order to try as (do not do next step until the prior has passed).

1. Ping host.domain.tld, get an ICMP response.

2. Execute delv host.domain.tld. and ensure that the first output line shows ; fully validated; please note the period (.) added at end of your hostname.

3. Exercise proper EDNS(0) using this EDNS(0) online tester against your server in question.

4. Get the SSH fingerprint from your SSH server in question to start the comparison; execute ssh-keyscan -D host.domain.tld. (note the -D option).

$ ssh-keyscan -D host.domain.tld.

which outputs:

host.domain.tld IN SSHFP 4 1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
host.domain.tld IN SSHFP 4 2 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

5. From a DNS query of the authoritative nameserver that is holding the SSHFP in its zone database file, obtain the SSHFP record using delv host.domain.tld. SSHFP.

$ delv host.domain.tld. sshfp

generates the following output:

; fully validated
host.domain.tld.        86400   IN  SSHFP   1 1 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
host.domain.tld.        86400   IN  SSHFP   1 2 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXX
host.domain.tld.        86400   IN  SSHFP   3 1 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
host.domain.tld.        86400   IN  SSHFP   3 2 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXX
host.domain.tld.        86400   IN  SSHFP   4 1 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
host.domain.tld.        86400   IN  SSHFP   4 2 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXX

6. Compare actual SSH fingerprint with the what the SSHFP DNS record says. The algorithm (1-6) and hash ID (1 or 2) must both match as well.

The algorithm ID to name that must match are: 1=RSA, 2=DSA, 3=ECDSA, 4=Ed25519, 6=Ed448.

The hash ID to name that must match are: 1=SHA1, 2=SHA256.

7. Try ssh -oVerifyHostKeyDNS=yes -oStrictHostKeyChecking=yes host.domain.tld. If this step works, integrate both options into your SSH client config file.

If the fingerprints do not match, it is always invariably the DNS record that needs updating.

WARNING Appeared

With newer OpenSSH, you might even get the following pesky prompt during an initial SSH login:

ssh host.domain.tld

may outputs the following:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ED25519 key sent by the remote host is
SHA256:XxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXx.
Please contact your system administrator.
Update the SSHFP RR in DNS with the new host key to get rid of this message.
Warning: Permanently added '[host.domain.tld.]:22,[999.999.999.999]:22' (ED25519) to the list of known hosts.
</etc/motd content goes here>
[email protected].'s password: 

The key thing to note in the above output is the following line:

Update the SSHFP RR in DNS with the new host key to get rid of this message.

It means exactly what it means.

The VerifyHostKeyDNS yes in your local SSH client config is what controls that output; the config being either in $USER/.ssh/config or in /etc/ssh/ssh_config.

The above decision is based on a simple comparison between:

• authoritative nameserver holding the SSHFP zone data of this host.domain.tld
• The SSH server of host.domain.tld providing the public key

This message covers 99.999% of the following potential scenario.

• sshd is not using the same pubkey, possibly due to:
  • a different pubkey has been generated via ssh-keygen (most common)
  • a different set of config file (via sshd -c <config_file>)
  • AuthorizedKeyFile had been change
  • fingerprint hash (FingerprintHash) setting had been changed
  • PubkeyAcceptedKeyTypes had been changed
  • CASignatureAlgorithms had been changed
  • TrustedCAUserKeys had been changed

The other 0.001% of the time is broken down in one of the many not so common scenarios:

• points to a different SSH server
  • a new port number has been opened (legitmately or not). This can happen if your ssh_config/$HOME/.ssh/config has used a different port number (rare but has maliciously happened)
  • a (different?) Dockerized container reusing same IP address
  • MAC address has been changed to point to a cloned server
  • IP filter (or nftables) rerouted your usual SSH port
  • IP route has been changed (by route table or by various IP route protocol like BGP, OSPF, RIP)
  • a ghost daemon appeared such that your server's rouge sshd daemon got its start through SysV init (service XXXX start or systemd start XXXX.service or system start XXXX.timer or furtively via crond/atd job or even rc.local) and is using its own SSH server public key.
• points to a different sshd executable. This requires file validation by package tools (of your distro in ascertaining that it’s checksum value, modification time, file path, security context, and attributes of not only the sshd executable file but its referenced libraries (see ldd/usr/sbin/sshd) are all computed and set correctly.

At any rate, once you've eliminated the remaining 0.001%, it is a simple matter of:

• Generate new SSHFP DNS record (ssh-keyscan -r host.domain.tld); save the output to an editor buffer
• Identifying the authoritative nameserver of domain.tld (dig domain.tld. soa and note the MNAME portion of SOA record data).
• Log in as root on that MNAME authoritative nameserver of host.domain.tld
• go to the correct config file of nameserver (ISC Bind9 is /etc/named.conf; newer Bind v9.11+ shows default config via named -V)
• Note the database file name of the domain.tld zone. (ISC Bind9 is file /var/lib/bind/db.domain.tld)
• change the directory to where that zone database file is located at
• Edit the db.domain.tld file.
• paste the new SSHFP DNS records from the editor buffer that you saved in the first step.

Might want to put that period (.) symbol directly at the end of the host name for each of these SSHFP data records (that was generated by ssh-keyscan before closing that zone database file; such that:

; note the extra ending period '.' after hostnames
host.domain.tld. IN SSHFP 4 1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
host.domain.tld. IN SSHFP 4 2 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Enjoy!

Source:

• https://fanf.livejournal.com/130577.html
• https://egbert.net/blog/articles/dns-rr-sshfp.html