After long time without updating them I decided to refresh my SSH and DNS use of SSHFP records which I succsefully used in the past long time ago.
So I configured my ssh_config to fetch host keys from DNS SSHFP records and I generated the SSHFP records using ssh-keygen -r (about 8 records per host using openssh version 7) and uploaded to the DNS:
$ ssh-keygen -r
wigan.l3jane.netwigan.l3jane.net IN SSHFP 1 1 4ea16c946b78c407ed62733bb3ec9d3f90b05ddf
wigan.l3jane.net IN SSHFP 1 2 5c39b2e106dea35232b0f8cd5e55b2f9391058e81c2247bc123f7960031209e0
wigan.l3jane.net IN SSHFP 2 1 76c7ca61d7364afd515470ac35f7b111b2b91de2
wigan.l3jane.net IN SSHFP 2 2 7effb058b4922a079131f1daa596a3288a7f73606fa4d388e0efa8f583f6e6e9
wigan.l3jane.net IN SSHFP 3 1 b9f56d258edf02c05eefb57f757ce517128cc32d
wigan.l3jane.net IN SSHFP 3 2 c6439507e4fc6de0e9d0381efe4851c1696927c938a61ffd715752f3cd87d035
wigan.l3jane.net IN SSHFP 4 1 6067c78156c5c12829069975caca5fbf4821b1a7
wigan.l3jane.net IN SSHFP 4 2 a76720d1b8f254e158f8b4c1193040c2ca10383aa9851d0fea3935ca7bdacdcd
; <<>> DiG 9.10.3-P4-Ubuntu <<>>
wigan.l3jane.net sshfp +noall +answer
;; global options: +cmd
wigan.l3jane.net. 3600 IN SSHFP 4 1 6067C78156C5C12829069975CACA5FBF4821B1A7
wigan.l3jane.net. 3600 IN SSHFP 3 2 C6439507E4FC6DE0E9D0381EFE4851C1696927C938A61FFD715752F3 CD87D035
wigan.l3jane.net. 3600 IN SSHFP 4 2 A76720D1B8F254E158F8B4C1193040C2CA10383AA9851D0FEA3935CA 7BDACDCD
wigan.l3jane.net. 3600 IN SSHFP 2 1 76C7CA61D7364AFD515470AC35F7B111B2B91DE2
wigan.l3jane.net. 3600 IN SSHFP 1 2 5C39B2E106DEA35232B0F8CD5E55B2F9391058E81C2247BC123F7960 031209E0
wigan.l3jane.net. 3600 IN SSHFP 3 1 B9F56D258EDF02C05EEFB57F757CE517128CC32D
wigan.l3jane.net. 3600 IN SSHFP 2 2 7EFFB058B4922A079131F1DAA596A3288A7F73606FA4D388E0EFA8F5 83F6E6E9
wigan.l3jane.net. 3600 IN SSHFP 1 1 4EA16C946B78C407ED62733BB3EC9D3F90B05DDF
However when I try to ssh to the hosts using VerifyHostKeyDNS yes, ssh always warn me that the keys don't match and to contact administrator to update SSHFP records:
$ ssh
wigan.l3jane.net@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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 ECDSA key sent by the remote host is
SHA256:+I0aL8rLHidzOoy5JzgY/k56ZNdmZ7jUylO60P6mo4o.
Please contact your system administrator.
Update the SSHFP RR in DNS with the new host key to get rid of this message.
The authenticity of host '
wigan.l3jane.net (172.31.108.132)' can't be established.
ECDSA key fingerprint is SHA256:+I0aL8rLHidzOoy5JzgY/k56ZNdmZ7jUylO60P6mo4o.
No matching host key fingerprint found in DNS.
$ ssh -V
OpenSSH_7.2p2 Ubuntu-4ubuntu2.2, OpenSSL 1.0.2g 1 Mar 2016
I confirmed with a tcpdump that the DNS server is answering correctly with all the possible keys, the only strange thing is that some fingerprint appear with a space in the dig DNS answer (although this space doesn't appear on the TCP capture, so I understand is the way dig shows the information).