A chave é gerada aleatoriamente. Não há nada mais especial em sua origem do que isso. Isso significa que enquanto você mantiver a chave privada, não há necessidade de substituí-la.
No SSH, uma chave de usuário é geralmente usada para identificar uma combinação de usuário & sistema de origem. O que significa que a chave não é compartilhada entre usuários no mesmo sistema ou o mesmo usuário em vários sistemas. Embora isso não seja uma limitação técnica, você pode quebrar qualquer uma dessas regras sem problemas. É apenas uma boa prática de segurança.
Em uma chave pública ( id_rsa.pub ), o último campo é um comentário. O comando ssh-keygen geralmente coloca seu nome de usuário & hostname como o último campo. Isso não tem outro propósito senão como um comentário para identificar a chave. Por que isso coloca o nome de usuário & hostname, veja o parágrafo anterior.
Para responder diretamente à sua pergunta, "Quando devo regenerar os pares de chaves?":
Você deve regenerar a chave quando a chave foi comprometida e potencialmente obtida por outra pessoa. Neste momento, você também deve revogar a chave pública anterior de todos os sistemas remotos que confiam nela (o arquivo authorized_keys ).
Isso é literalmente a única razão. Se você reinstalar o sistema operacional, alterar o nome do host, etc, não será necessário recriar a chave. Embora você possa, se quiser.