Well, sshd just wasn't running. For some reason, android-gadget-service didn't actually do anything. I've started sshd manually by running sudo /etc/init.d/ssh start and it works.
Info I've gathered when trying to determine if it's running:
I've run sudo lsof -i -n -P | grep LISTEN on the phone to know if port 22 is open, but it wasn't in the output, which means nothing is listening on it.
Then I've run sudo ps aux | grep ssh and no matter if ssh is enabled or not it reports process from /usr/bin/ssh-agent /usr/bin/dbus-launch --exit-with-session ubuntu-touch-session command to be in the interruptible sleep (Ss in the STAT column). It doesn't report anything else, except grep --color=auto ssh due to results being filtered by grep.
Now, as I started it, the output also contains /usr/sbin/sshd -D -o PasswordAuthentication=no.