Esse problema geralmente é causado por não ter o arquivo PEM de chave privada correto adicionado ao seu agente ssh local. Fazendo algo como:
$ ssh-add pk-XXXX
Onde o argumento é a parte privada do par de chaves usado para criar a instância do EC2.