Hmmz... and you're sure openssl is installed too correctly? And you're logged in as full root?
I don't think it's an image question, because the image only installs the OS and then it's up to the OS to decide what's possible and what not.
I don't know which kind of key you generated. I use SecureCRT, however that's a paid application, and imho it's worth it's costs but I had to change keys some time ago too. It required another kind of keypair. Maybe that is the cause.
Maybe try using a RSA 2048 or ECDSA 2048 keypair and see if that works.
Otherwise I'm prepared to have a short look for you (for free) and test if some keypair of mine will work, however that would mean I have to login to your server, not everybody is prepared to have this done. If yes you can contact me by pm.