Uma maneira fácil é usar o encaminhamento de porta ssh:
ssh -L 3389:winhost.com:3389 [email protected]
onde winhost.com é o nome do host do seu servidor windows (deve ser acessado pelo servidor linux, ou seja, não bloqueado pelo firewall). Em seguida, você se conectaria ao host local ou 127.0.0.1 em vez do host do Windows para criar uma conexão RDC.
Funciona como um encanto aqui.