Are you able to run ssh directly and connect / comm with the server? (if you have an account with terminal access). That would distinguish between a dulwich and paramiko problem.
Can you verify the paramiko version you are using? Likely you need 1.16.
Are you able to try https, at least for the initial clone?
Another check, trying ssh with a small repo:
[~/Documents]$ mkdir blah
[~/Documents]$ cd blah
[blah]$ git init .
[blah]$ git commit blah blah blah
d8192599eff9eab370a6c2052b74a4d03419a59c
[blah]$ git branch
* masterd819259
[blah]$ git branch blah
[blah]$ git checkout blah
[blah]$ git branch -D master
deletemaster['master']False
removing master (was d8192599eff9eab370a6c2052b74a4d03419a59c)
[blah]$ git remote origin ssh://yourserver
[blah]$ git push
(if you have the ability to create a new repo, that would be simpler and safer, the above is to try to avoid nuking master, by creating a new, empty branch, then pushing that... though if you can create a new repo, try cloning a repo with only 1 commit.)
If that works, then the issue is maybe just the big initial clone. try git fetch, or use https for initial clone.
if maybe the large clone is the issue: try:
git init somefolder
cd somefolder
git branch -c newbranch
echo test>test.txt
git add test.txt
git remote origin ssh://yourserver