Se sua loja usa uma ferramenta de gerenciamento de configuração, como Puppet, CFEngine, Chef, etc, essa seria a maneira mais fácil.
Se não, mas você tem um serviço de diretório que faz o LDAP, existe uma extensão para o OpenSSH para armazenar chaves públicas no diretório.
Por fim, você pode envolver as chaves públicas em um RPM e distribuí-las como se fosse um software. Isso também ajudaria com o gerenciamento do ciclo de vida, como substituir, adicionar, remover chaves são essencialmente resolvidos problemas.