A seguinte linha pode ser uma mensagem muito enganadora:
debug3: Could not load "/home/chris/.ssh/id_rsa" as a RSA1 public key
debug2: key_type_from_name: unknown key type '-----BEGIN'
Ele enviará você em uma perseguição selvagem. Eu digo que, dado que você passou por todos os diagnósticos e até regenerou a chave, o problema persistiu.
Por experiência, posso dizer que esse problema pode ser causado pela configuração do servidor, mesmo que as mensagens pareçam estritamente um problema de chave do cliente.
Para resolver isso, verifique cuidadosamente a configuração do SSH do servidor. Neste caso, primeiro certifique-se de ter adicionado o conteúdo do id_rsa.pub à sua conta do Git. Verifique outras permissões lá.
Quando isso acontecer no seu próprio servidor, verifique a configuração com cuidado. Por exemplo, descobri que se o seu usuário não é permitido pela configuração do ssh no servidor, o cliente ssh dá exatamente a mesma mensagem de erro (enganosa).
sudo nano /etc/sshd_config
AllowUsers yourname@*