Sounds like a job for dnssec and sshfp records

Ahh, now you have three problems…hrm