¿Has mirado que el PC linux tenga un servidor SSH activo?

Si está en diferentes redes mira que el router suelen tener el puerto 22 cerrado, debes ir al router al que esé conectado el PC servidor, en este caso supongo que es el Linux, y abrir el puerto y direccinar esas conexiones al puerto 22 del servidor SSH.

Al tener ususario y contraseña supongo que el PC linux tiene un servidor, pero ten en cuenta que los usuarios y contraseñas SSH no son los mismos que los usuarios de Linux, revisa los usuarios que creastes cuando instalastes el servidor.

Ahora mismos no se me ocurren más cosas que puedan fallar.

Al Arduino lo puedes aimentar sin problemas con 9V y creo que hay modelos que hasta 12V (no estoy seguro 100%), y si te fijas, hay un pin que pone Vin (junto a los GND V5 V3.3), ese pin saca la tensión con la que alimentas al Arduino, así que si lo alimentas con un alimentador de 9V en vez de por el USB ese pin te sacará 9V, puedes tener el USB conectado al PC y se está alimentando y con el alimentador a la vez, pero solo le das 9V tiene un limitador, no te preocupes por ello.

Si que es verdad que se suelen quemar con cierta facilidad. Pero yo he llegado a tener el mio 4 meses coenctado con un alimentador de 9V y no se me ha quemado ni nada, así que mientas no te excedas con la alimentación no creo que tengas problemas.

En cuanto al relé o transistor pues no se decirte, nunca he trabajado con motores con él, pero si que tendrés que colocar algo que pare la corriente electromotriz que genera el motor al ponerse en marcha, eso si que puede quemarte el Arduino. Yo apostaria por un transistor si mal no recuerdo, pero eso mejor que lo conteste alguien que controle más de electronica, yo la tengo un poco abandonada.