Não há uma resposta correta única. Em um sistema de tamanho médio, criei um servidor central e scripts para empurrar e manter a infraestrutura ssh. Existem, no entanto, limites de escala para isso - as arquiteturas de push não escalam tão bem quanto as de pull.
O próximo passo é usar algo como fantoche, chef ou cfengine para implantar uma arquitetura baseada em pull.
Você também pode se mover em direção a um sistema baseado em LDAP (até mesmo armazenar chaves ssh no LDAP) - por exemplo, link ou mover para um mecanismo de autenticação diferente - o SSH suporta alguns.