Você só precisa realmente de um banco de dados se tiver mais de 1.000.000 de entradas. Cada chave é bem pequena (nem mesmo um kilobyte). Contanto que o arquivo seja menor que, digamos, 20 megabytes, a leitura no arquivo é trivial (estamos falando de milissegundos aqui). Seu maior problema é o balanceamento de carga. Se você tiver centenas de usuários simultâneos, terá problemas com recursos muito rapidamente.
Seu caso de uso (1000 chaves) resultaria em cerca de 400 kilobytes de arquivo de chave ssh. Nada de muito importante. Demorou 30 meses para o meu script coxo ler esse arquivo. Duplique ou triplique para analisar e ainda não é grande coisa.
Você precisará obter outro servidor para lidar com a carga antes de ler no arquivo de texto se tornaria um problema.
Na palavra do servidor, grande é relativo. 500.000 não é um grande problema para analisar um arquivo de texto. Por exemplo, meu arquivo id_rsa.pub tem 400 bytes. Não é grande em tudo. Vamos multiplicar isso por 500.000. Ficamos com 190 megabytes. Isso é relativamente grande, mas não muito grande. Escrevi um script NodeJS simples para ler em um arquivo de 174 megabytes de tamanho e levou menos de dois segundos. Isso está em um disco rígido regular (não de classe de servidor) (7200 RPM), e nem mesmo em uma invasão.
O SSH não precisa ler todo o arquivo toda vez, e o arquivo provavelmente seria armazenado em cache na memória. Em ambos os casos, alguns segundos de tempo de carregamento não são um grande problema para um processo único como o acesso SSH.
A beleza por trás do github é que os usuários não têm acesso SSH. Os usuários podem apenas enviar código e não podem se conectar diretamente ao servidor. Este é, obviamente, um problema de segurança, mas é definitivamente um problema de desempenho também.
Tenho certeza de que lugares como o github têm alguns servidores para lidar com a carga.