SSHFP Records are DNS records that allow you to publish fingerprints of your servers so they can be verified using DNS lookups when you connect to them. This can be done in a public or using an internal DNS server. Using this method will also stop you from blindly adding machines to your known_hosts file. Its also far quicker than manual verification and checked everytime.
There is lots of software on the internet that allows you to generate SSHFP records however the easiest way is to run the command from the server you wish to validate a connection to making sure you have the public key installed.
To get started login to the server with the key installed and run the command:
ssh-keygen -r example.com
The records will be produced in the correct format. You don't need to include the shorter hashes as these are sha1. You can now add these hashes to your DNS zone.
To ensure the keys are checked on the client you want to connect from edit the following file:
sudo nano /etc/ssh/ssh_config
add the following line as shown below:
Now connect using the -v command so you see the debug output (leave -i if you don't use a key pair).
ssh -v firstname.lastname@example.org -i test
You will see in the debug that the keys were found in dns: