Is it possible that you are using a dsa key? ;-) Use ssh with -v and take a look to the Output.
Yes, that was the problem. I switched to rsa, which doesn't seem to me like it reduces paranoia, but I deal with systems that apparently don't understand ed25519.
