ssh VerifyHostKeyDNS not working I'm stuck figuring out why ssh is unable to verify my SSHFP entries.
VerifyHostKeyDNS=yes is set in my ~/.ssh/config  


The Zone is properly signed as verified with
https://dnssec-analyzer.verisignlabs.com.
SSHFP entries have been generated with ssh-keygen -r myhostname
dig +dnssec myhostname.myzone.tld answers with the proper RSIG entries and the do flag set (tested with internal resolver (pfsense) and external (quad1, quad8, quad9))


I have tested everything with my Ubuntu 18.04 machine and can verify that it works (DNSSEC and SSH key verification), but my MacBook "thinks different"…

debug1: Server host key: ecdsa-sha2-nistp256 SHA256:tV75nOBtVSASQEc4Ruf3iwBDAokvusd8BnLsfIWrzPQ
debug1: found 6 insecure fingerprints in DNS
debug1: matching host key fingerprint found in DNS
The authenticity of host 'myhostname.myzone.tld (192.0.2.1)' can't be established.
ECDSA key fingerprint is SHA256:tV75nOBtVSASQEc4Ruf3iwBDAokvusd8BnLsfIWrzPQ.
Matching host key fingerprint found in DNS.
Are you sure you want to continue connecting (yes/no)?


I had the same issue on my Ubuntu Machine as systemd-resolved had DNSSEC not enabled. 
But macOS's mDNSResponder has no options at all.
Could it be that macOS Catalina has no DNSSEC support (yet?/enabled by default?)


System: macOS Catalina 10.15.1
Local Resolver: pfsense (unbound)


$ uname -a
Darwin MacBook.home 19.0.0 Darwin Kernel Version 19.0.0: Thu Oct 17 16:17:18 CET 2019; root:xnu-6153.41.3~29/RELEASE_X86_64 x86_64
$ ssh -V
OpenSSH_7.9p1, LibreSSL 2.7.3
As it appears you know, you have to get your DNS entries and resolver to support DNSSEC before VerifyHostKeyDNS can possibly work. 

This line in your output

debug1: found 6 insecure fingerprints in DNS


tells us that ssh found the the DNSSEC entries but did not trust them. This is most likely because it correctly asked for Authenticated Data (otherwise it would not find fingerprints at all) but the DNS resolver did not indicate the results were authenticated (otherwise the fingerprints would be labeled "secure" not "insecure").

First thing to do is verify that dig can validate your DNS by looking for the ad flag in the results of dig, like this (parts of the reply omitted for brevity):

$ dig +dnssec @1.1.1.1 icann.org

; &lt;&lt;&gt;&gt; DiG 9.8.3-P1 &lt;&lt;&gt;&gt; +dnssec @1.1.1.1 icann.org
; (1 server found)
;; global options: +cmd
;; Got answer:
;; -&gt;&gt;HEADER&lt;&lt;- opcode: QUERY, status: NOERROR, id: 17489
;; flags: qr rd ra ad; QUERY: 1, ANSWER: 2, AUTHORITY: 0, ADDITIONAL: 1

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags: do; udp: 1452
;; QUESTION SECTION:
;icann.org.         IN  A

;; ANSWER SECTION:
icann.org.      587 IN  A   192.0.43.7
icann.org.      587 IN  RRSIG   A 7 2 600 20191202002438 20191110134355 8150 icann.org. W9PTVWEF4Dd6fQmPRmaq9n7IMCds3JSRks1GB+JBHzrL63OX2QMZ7o1X YSZb90Rr6m2Di7ckcBiZtp/JGwvwEN2xPfWc5XubFsfQ8Vxpdze3o6DK llilOoHxrdTtnvYQ2djV+pWBoIkmX+eIKJSEhofy/c5K95nLxQ51RYBB AfU=


Note that ad (Authoritative Data) appears in the list of flags. This tells you that dig was able to validate the integrity of the data via DNSSEC. From the comments on the question, it appears that you are not seeing the ad flag, and so you need to address that by verifying that your DNSSEC keys are all correctly set up and that your DNS server supports DNSSEC. This includes making sure that your local DNS server has the correct root keys for validating the DNSSEC chain of trust.

Some other notes

Once you get the ad flag from dig, you still need to be mindful of the fact that, as noted in the dig man page on the Mac, dig uses its own query system, not the system-wide one, so all dig can really verify is that you have your DNS entries correctly set up on your name server and that the DNS server you are contacting support DNSSEC. For that matter, ssh does not necessarily use the system DNS either, although in your case it appears to be.

Also, from a security perspective, you still have the issue of trusting the DNS server you are talking to. Unless you also set up some kind of authentication between your host and the DNS server, you remain vulnerable to a man-in-the-middle attack.