Can not connect to SSH with Public Key!

[Patschi]

Everytime I try to connect to my server with a public key I got following message:

[20:23:52] [R] Connecting to root -> IP=000000 PORT=0000
[20:23:52] [R] Connected to root
[20:23:52] [R] Host key algorithm ssh-RSA, size 2048 bits.
[20:23:52] [R] Fingerprint (MD5): 000000
[20:23:52] [R] Key exchange: diffie-hellman-group14-sha1. Session encryption: aes256-ctr, MAC: hmac-sha1, compression: none.
[20:23:52] [R]
[20:23:52] [R] Auth Type: Public Key
[20:23:53] [R] Authentication failed [Public Key]
[20:23:53] [R] SSH Error: failed to negotiate authentication method [Public Key]
[20:23:53] [R] SSH Connection closed
[20:23:53] [R] Connection failed

I tried all I could, still not working!

My SSH key is 15 KB big, but Host key will be shown 2048 bits. Could that be the problem?