This answer was copied from https://serverfault.com/questions/854208/ssh-suddenly-returning-invalid-format/984141#984141

In my case, it turned out that I had newlines between the start/end "headers" and the key data:

-----BEGIN RSA PRIVATE KEY-----

- Key data here -

-----END RSA PRIVATE KEY-----

Removing the extra new lines, so it became

-----BEGIN RSA PRIVATE KEY-----
- Key data here -
-----END RSA PRIVATE KEY-----

solved my problem.