Sounds good in theory. Now, say I want to use github over ssh, how do I check if the randomart image is correct? (Getting my configs from github tends to be the first thing I do on a new machine.)
The CA approach is probably good if you control the servers you use. Right now I connect to about 5-7 ssh servers on a regular basis, and I don't have (full) control over any one of them.
`ssh-keyscan -t rsa github.com | ssh-keygen -lf -` gives you the fingerprint for github.com.
Save this key, and reuse it everywhere before connecting to github.
Now the issue of being MITM'd is once again only an issue with your very first connection, which is done via ssh-keyscan.
As for your other servers, you should only check the host key once for any of them, and then save it. And that's only if they are owned by a third-party, like a shared server. If your provider routinely cycles host keys, get a new provider who actually cares about security.
If these servers are owned by your employer, then your employer needs better security practices and, failing a certificate authority, should provide you with the necessary host fingerprints before you ever connect to a box.
I currently check fingerprints on first connection and then save them. They're available for most servers, including github and other git providers. I think I've only had to connect to one server without knowing the fingerprint in advance in the last couple of years.
Looks to me like the fingerprint-checking process has to be manual if you can't choose the server certificate.
The CA approach is probably good if you control the servers you use. Right now I connect to about 5-7 ssh servers on a regular basis, and I don't have (full) control over any one of them.