What exactly does ssh-add do?
Solution 1:
ssh-add adds private key identities (from your ~/.ssh directory) to the authentication agent (ssh-agent), so that the ssh agent can take care of the authentication for you, and you don’t have type in passwords at the terminal.
Solution 2:
Based on this article in github, sometime on some linux distributions even after you set up everything properly this error shows up:
Agent admitted failure to sign using the key.
debug1: No more authentication methods to try.
Permission denied (publickey).
And you should run ssh-add to solve the issue.