Ask HN: How do you manage SSH known_hosts?

In our company we are managing a few dozen virtual machines. A lot is automated, but we still need to manually ssh in to machines often.

How do you manage your ~/.ssh/known_hosts file, to make sure you're not connecting to a malicious host? We spin up machines often, and it's not feasible to manually check every new host key. Additionally, DNS entries are often updated to new hosts, which produces nasty "WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!" messages, which some people also learn to ignore after a while.

Are there any tools to keep a company-wide known_hosts file in sync? Or should we not be using SSH directly to all these machines at all?