Why am I getting "Permission Denied" when running ssh-add?

You want both the key folder and the key itself to only be readable by the user. I always do chmod 700 ~/.ssh; chmod 600 ~/.ssh/* myself, where you'll obviously want to change those directories to suit your own use case.

Alternatively, you can chown -R $USERNAME ~/.ssh; chmod -R go-rwx ~/.ssh

The chown can be necessary when the key file was downloaded or installed as root for instance.

Never do a chmod 777 on your private key! It makes it (possibly) publicly readable, and you don't want that. Furthermore, SSH will in some cases even refuse to use a file with too permissive permissions, so you could be shooting yourself in the foot with this.

If the file's permissions aren't the issue, there can be several other causes. You could have incorrect permissions set on any of the directories ~/.ssh or ~/.ssh/keyfolder (technically also on ~ but then this wouldn't be the only symptom). Use ls -adl to inspect those directories. They should have rwx for you, but --- for both group and world.

Another issue could be (but this is quite rare) is that the ssh-add binary has the setuid bit set, causing it to run as a different user, and hence have no right to read your private key. Use ls -lh $(which ssh-add) to inspect this.

The first thing to do in this situation is to use the -v option to ssh (adding verbose), so you can look into what types of authentication methods are being tried and what the result is. This may give a subtle information of the possible wrong things that may be going into it. Then you look into the answer given by Sybren