You are logging with the wrong user
In my case, I was trying to connect to an Amazon AWS EC2 instance, but getting the error
load pubkey "MyPrivateKey.pem": invalid format
This was because I was trying to log with the wrong user (ec2-user)
I was using an Ubuntu machine, with user ubuntu instead of ec2-user (as is stated on the official Amazon Linux server OS).
But why that error?
It turns out Amazon uses an old format (puttygen says upon loading "openssh ssh-2 private key (old pem format)") that openssh doesn't like very much, so it is really a warning and not an error.
The real error (there is no such user on that server) is hidden by the server (otherwise you could brute force login names), but instead a "Connection closed" is shown.
You can find the name you use to connect to your machine on AWS under Actions>Connect.
How to fix the warning?
Just follow the answer of "Ras", which is, use PuTTYgen to convert to the OpenSSH format.