TL;DR: also ensure that your id_rsa.pub
is in ascii / UTF-8.
I had the same problem, however the accepted answer alone did not work because of the text encoding, which was an additional, easy-to-miss issue.
When I run
ssh-keygen -f ~/.ssh/id_rsa -y > ~/.ssh/id_rsa.pub
in Windows PowerShell, it saves the output to id_rsa.pub
in UTF-16 LE BOM encoding, not in UTF-8. This is a property of some installations of PowerShell, which was discussed in Using PowerShell to write a file in UTF-8 without the BOM. Apparently, OpenSSH does not recognise the former text encoding and produces an identical error:
key_load_public: invalid format
Copying and pasting the output of ssh-keygen -f ~/.ssh/id_rsa -y
into a text editor is the simplest way to solve this.
P.S. This could be an addition to the accepted answer, but I don't have enough karma to comment here yet.