It's amazing to me how many people use ssh and don't have an ssh config. It would be easier to maintain a .ssh folder in version control then to install this on each host and ssh until it learns.
Your auto provision of servers with chef or puppet should be adding them to you .ssh/config with a pointer to the ssh key and special requirements like tunnels through jump hosts/ bastion hosts.