key_load_public: invalid format with scp or git clone on Ubuntu 15.10

Check the file /Users/alexzeitler/.ssh/id_rsa. What is there? How did it get there?

It should be your private RSA key, isn't it? And is there something in /Users/alexzeitler/.ssh/id_rsa.pub? Is it valid public key?

If you don't use these keys, remove both of them and the message will disappear. If you are using them in different way, move them somewhere else. The same if they are in different format.

The public part is probably corrupted, so you can recreate it from private one using this command:

ssh-keygen -f ~/.ssh/id_rsa -y > ~/.ssh/id_rsa.pub

###hostkeys possibility The other possibility is that client is trying to read server public keys for HostBasedAuthentication. Don't you have it allowed in /etc/ssh/ssh_config ?

It would be one of these files missing or corrupted:

/etc/ssh/ssh_host_ecdsa_key.pub
/etc/ssh/ssh_host_ed25519_key.pub
/etc/ssh/ssh_host_dsa_key.pub
/etc/ssh/ssh_host_rsa_key.pub

Your sshd server is not complaining?