Ok, after some minutes of heavy google digging, I finally found a way to get my gpg key to work with ssh:

1. Install "gnupg2"; (it provides the gpgkey2ssh tool)
2. Import your ascii-armored public key onto the target system by doing a "gpg —import bla.asc"; (where bla.asc is your public key. Mine looks like this)
The resulting output will look something like this:

gpg —import marcpub.asc
gpg: key 7C88836C: public key "Marc Seeger "; imported
gpg: Total number processed: 1
gpg: imported: 1

3. use "gpgkey2ssh YOURKEYID"; (in my case: gpgkey2ssh 2C18494C7C88836C) to get the correctly formated key for ssh usage.

gpgkey2ssh 7C88836C
ssh-dsa AAAAB3NzaC1kc2EAAACBALqkBwfJgtlfpkbNsvcA0drBAsVN70R626VmNovo/hWuCBocfb3whzqcMpq5HP+Y4b7U6LCQsU/aqxSdvmjMJMKCsAAd0unn7d7sH43wPvK2MUSLjBotVDFQxymbLwZnZ9iksA/jrZVXulDy01GpIiRk3Pvdhvsb+QHEZweecD3XAAAAFQD5TIF3e8xX5smUzH3MQ0u59ar+cQAAAIEAst7c5xPOTBuQYKOYzRVYntsxnHuMiU2VSZf3Kq3Aa/AncBCxwC2mJe3HCU060liYGfpU0xTdN96schAfHpveqqbEdwGYI4W5xj8j1dhCzaA6xco63ZpjoXoDQwx74SN1iMOgOqsTzmZrbLvILU6HMtbVPUCol2dd0LyL3zQCDSoAAACAF8gLmx670iYewPlUF6CWpgCQnjTjuCO++32aTAhxJUdOZcWmTrJvqHC66pyg//QG1GVCa9E8wSUMuw0HfCUKDnIQwYuLcwxDNgGGpGO4hygXFrQFIsNZBVTIJGW1ts7vp0ZJV9CabLDVLrxw7rDpw+Oq/3wZUjN2fmM3YPfMUNs= COMMENT

4. Insert this into your .ssh/authorized_keys file (I put it on one single line). You can Change the "COMMENT"; part to something meaningful

Now I've gotta figure out a way to get my certificate into something putty can understand

UPDATE: and now from the client side