What I really want is decent PKI for ssh host keys so I can verify a key once, sign it, and have it respected by all other users/machines without further intervention.

I may try out MonkeySphere, anybody already use it?

Edit to add: MonkeySphere doesn't support options in authorized_keys, which is a bummer.