Enrico's known_hosts update strategy is nice, but:
These are relatively small flaws, and as a project debian is able to work around them because we have infrastructure in place like the machines database (though checking the machines db manually is tedious and therefore error-prone). But most other projects don't have that level of organization, and the process doesn't scale to other projects we (or our users) might be involved in. And other projects (including debian, i'd think) might prefer to have a less centralized process, to minimize bottlenecks and single points of failure.
Check out Monkeysphere's documentation for a server administrator for a quick rundown about how to easily publish your SSH host keys via the Web of Trust (it's not mutually-exclusive with the technique Enrico describes).
And this is just part of what the monkeysphere can do: using the same web of trust, monkeysphere is capable of helping a host authenticate ssh users based on their OpenPGP identities, which gives full re-keying and revocation functionality for these accounts. But that's a separate discussion!