Вам надо выяснить куда девается старый ключ.
Посмотрите в ~/.ssh , есть-ли ключ (id_rsa, id_dsa, etc), корректные ли на него права и т.д.
Ну и вообще проверьте как у вас подключение идёт
ssh git@github.com
если будет ошибка - добавьте ключ -vv
ssh -vv git@github.com