For many of our openssh servers we have their fingerprints in DNS (SSHFP). We do not yet use secure DNS, i.e. though the FP is in DNS, a connect like
ssh -o VerifyHostKeyDNS=yes <user>@sshserver
will be answered like
Matching host key fingerprint found in DNS.
and unfortunately, but in full accordance with man man ssh
Host key verification failed.
Since we have many external clients who come across this message it often invokes confusion and questions. Is there a way to change these messages?
The messages are hardcoded into the SSH client. So unfortunately without changing the messages in the source code, recompiling the binaries for all possible platforms and distributing those files to your clients, who then have to replace the official binaries with your modified version there is no way to do this.
Extract from sshconnect2.c: