Recently I faced an issue with circle CI related to “Checkout using deploy key”.
Initially It was working fine, at one point, I deleted the project Github repo and recreated a new repo with the same name.
Then I tried to build the application manually and things started failing, I got the error
Warning: Permanently added the RSA host key for IP address ‘126.96.36.199’ to the list of known hosts.Permission denied (publickey).
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists. git command i returned 128
Fix for the issue
Go to Project Settings under Checkout SSH keys there will be an option to remove deploy key, click on the remove button to remove the existing ssh key and recreate it.
Hope this will help someone.