A lot of suggestions to resolve such an issue hint at changing permissions of the ~/.ssh directory and the files it contains. More on this : https://gist.github.com/grenade/6318301
Some even suggest ssh-add which may not solve the issue and might be redundant.
Having tried both of the above, did not solve this problem for me. Instead, the problem was with the type of ssh key I was generating.
As @strudelj nudelj mentioned, it is important to check if the encryption type used by your public key is supported by the server you are connecting to. For example, a gitlab server I was trying to did not support the type of keys usually stored in ~/.ssh/id_dsa.pub
Instead, it required ed25519 or rsa encrypted keys.
For ed25519, one can use: $ssh-keygen -t ed25519 -C "[email protected]" to generate the key
Then, $ssh -T user@server should offer a good check if this key is accepted and a connection can be established.
Following this, helped solve a similar issue I was facing.
