By design, ssh does not make use of certificates. So there is no way for ssh to know upon connecting to a host for the first time whether the public key presented by that host is authentic. After the first connection, ssh caches the keys in ~/.ssh/known_hosts, and will then give you a big warning if the key changes. I imagine when this happens many folks blindly delete the the cached key and re-connect.
So you should be aware of the potential for MITM attacks to occur unless you have some out-of-band mechanism for distributing or authenticating host keys.
Edit: huh, apparently ssh added support for certificates. "ssh-keygen supports signing of keys to produce certificates that may be used for user or host authentication." So now you just need to distribute your CA certificate everywhere and you're golden. http://justanothergeek.chdir.org//2011/07/howto-authenticate...