(This is a up to date answer to an old question)
I got ssh based builds working with github/gitlab and teamcity 7 like this:
Log onto the teamcity machine and use puttygen/ssh-keygen to generate a rsa key pair and save the openssh key somewhere sensible.
(Gotcha - Using puttygen? Make sure the private key is in openssh format - puttygen > conversions > export openssh key)
I suggest you save the private key in
C:\.ssh\id_rsa
Now setup "default private key" in teamcity - create a file
C:\.ssh\config
And in it place this:
Host * IdentityFile c:\.ssh\id_rsa
Login to your gitlab/guthub account and paste in the openssh public key for your teamcity private key.
You should now be able to create a git vcs root in teamcity that can use the default private key to pull your source.