Vous voulez que le dossier de clés et la clé elle-même ne soient lisibles que par l'utilisateur. Je fais toujours chmod 700 ~/.ssh; chmod 600 ~/.ssh/* moi-même, où vous voudrez évidemment modifier ces répertoires en fonction de votre propre cas d'utilisation.
Vous pouvez également chown -R $USERNAME ~/.ssh; chmod -R go-rwx ~/.ssh
Le chown peut être nécessaire lorsque le fichier clé a été téléchargé ou installé en tant que root par exemple.
Ne jamais faire de chmod 777 sur votre clé privée ! Cela le rend (éventuellement) lisible publiquement, et vous ne le souhaitez pas. De plus, SSH refusera même dans certains cas d'utiliser un fichier avec des autorisations trop permissives, vous pourriez donc vous tirer une balle dans le pied avec cela.
Si les autorisations du fichier ne sont pas le problème, il peut y avoir plusieurs autres causes. Vous pouvez avoir des autorisations incorrectes définies sur l'un des répertoires ~/.ssh ou ~/.ssh/keyfolder (techniquement aussi sur ~ mais alors ce ne serait pas le seul symptôme). Utilisez ls -adl pour inspecter ces répertoires. Ils devraient avoir rwx pour vous, mais --- pour le groupe et le monde.
Un autre problème pourrait être (mais c'est assez rare) est que le ssh-add le binaire a le setuid bit défini, l'obligeant à s'exécuter en tant qu'utilisateur différent et n'ayant donc pas le droit de lire votre clé privée. Utilisez ls -lh $(which ssh-add) pour inspecter cela.