Quando uma conexão SSH é inicializada, o servidor se autentica no cliente. O cliente verifica se a chave já está no arquivo known_hosts. Caso contrário, irá avisar o usuário. É por isso que, na primeira conexão SSH, você recebe uma solicitação perguntando se deseja aceitar uma chave com impressão digital xyz. A chave pública dos servidores é então gravada no arquivo known_hosts.
Se você nunca tiver SSH ligado ao servidor, ele não estará no arquivo known_hosts e as conexões automáticas falharão. A maneira mais fácil de contornar esse problema é conectá-lo ao servidor como o usuário que deve sintonizar o comando git e responder "sim" no prompt.