O SSH validará o servidor com base na assinatura da chave pública usada (um simples hash). Cabe ao usuário certificar-se de que a assinatura é válida (ou seja, você normalmente precisa de um canal seguro para isso também; na prática, os clientes geralmente só lembram da primeira assinatura enviada pelo servidor e simplesmente avisam se essa assinatura mudou). p>
Isso significa que a validação do servidor (correta ou incorretamente) não será influenciada por sua seleção de algoritmo simétrico de criptografia.
Dito isso, posso garantir que a alteração da criptografia simétrica de AES para RC4 não trará nenhuma melhoria perceptível no desempenho: mesmo com um processador muito lento (ou deficiente), a diferença de velocidade entre os dois não serão notados.
Se você precisar de mais informações, alguém realmente realizou uma análise detalhada se os resultados de AES vs RC4 (incluindo vários modos de operação para AES)