Na sua sessão ssh, tente executar
export DISPLAY=:0
antes da chamada xrandr. Isso permitirá que o xrandr saiba usar a exibição local em vez daquela que você logou.
Então, você fará algo como:
$ ssh my_machine
...
$ export DISPLAY=:0
$ xrandr --output VGA1 --mode 800x600
Substitua VGA1
pelo nome da tela e 800x600
pela resolução desejada.