Desea que tanto la carpeta de claves como la clave en sí solo puedan ser leídas por el usuario. Siempre hago chmod 700 ~/.ssh; chmod 600 ~/.ssh/* yo mismo, donde obviamente querrá cambiar esos directorios para adaptarlos a su propio caso de uso.
Alternativamente, puede chown -R $USERNAME ~/.ssh; chmod -R go-rwx ~/.ssh
El chown puede ser necesario cuando el archivo clave se descargó o instaló como raíz, por ejemplo.
Nunca hagas un chmod 777 en su clave privada! Lo hace (posiblemente) legible públicamente, y no quieres eso. Además, en algunos casos, SSH incluso se negará a usar un archivo con permisos demasiado permisivos, por lo que podrías estar disparándote en el pie con esto.
Si los permisos del archivo no son el problema, puede haber otras causas. Podría tener permisos incorrectos establecidos en cualquiera de los directorios ~/.ssh o ~/.ssh/keyfolder (técnicamente también en ~ pero entonces este no sería el único síntoma). Usa ls -adl para inspeccionar esos directorios. Deberían tener rwx para ti, pero --- tanto para el grupo como para el mundo.
Otro problema podría ser (pero esto es bastante raro) es que el ssh-add binario tiene el setuid bit establecido, lo que hace que se ejecute como un usuario diferente y, por lo tanto, no tiene derecho a leer su clave privada. Usa ls -lh $(which ssh-add) para inspeccionar esto.