O tamanho da chave RSA só importa no momento em que a conexão é estabelecida. O tamanho da chave pode ser importante se uma das máquinas for lenta, pois as chaves maiores significam cálculos mais longos, mas seu impacto nos tempos de conexão é insignificante.
Se a taxa de transferência for um problema, comprima a conexão: ssh -C
.
Se o horário de estabelecimento da conexão for um problema, certifique-se de ativar uma única conexão SSH principal e usar o modo escravo para as conexões subsequentes.
Se a latência for um problema, não há muito que você possa fazer além de adaptar seus hábitos. Se a latência é tão alta que os programas interativos são difíceis de usar, digite comandos localmente e envie-os quando terminar (o modo shell do Emacs é bom para isso). Faça o gerenciamento de arquivos através de SSHFS (exceto cópias remotas para remotas).
Evite a necessidade de X remoto, pois é sensível à latência e consumo de largura de banda. Se você realmente precisa, NX é o melhor da safra (mas é difícil de configurar porque não é software livre, então distribuições não fornecê-lo, isso pode mudar como clones livres estão surgindo).