Ok so I have now tried with no passphrase and still getting the same, much like MartinK.
I have in desperation also tried switching all my firewalls off and using the ssh-key from my host machine and uploading from there.

Is anybody getting any luck adding a new key to garage?