Tramp can't connect - cannot find ssh

Question

I am trying to use Tramp, but it seems unable to execute the ssh command.

Here is the error from *Messages*:

Tramp: Opening connection for AWS2 using ssh...
Word wrapping enabled
Tramp: Sending command ‘exec ssh   -o ControlMaster=auto -o ControlPath='tramp.%C' -o ControlPersist=no -e none AWS2’
Tramp: Waiting for prompts from remote shell...
Tramp failed to connect.  If this happens repeatedly, try
    ‘M-x tramp-cleanup-this-connection’
Tramp: Waiting for prompts from remote shell...failed
Tramp: Opening connection for AWS2 using ssh...failed

and this appears briefly in a pop-up buffer:

/bin/sh: 1: exec: ssh: not found

which makes me think it might be something to do with the PATH that Emacs is getting.

---

The contents of the auto-generated tramp file inside ~/.emacs.d/, which I have deleted and was recreated:

;; -*- emacs-lisp -*- <20/07/16 14:53:07 /home/user/.emacs.d/tramp>
;; Tramp connection history.  Don't change this file.
;; You can delete it, forcing Tramp to reapply the checks.

(((tramp-file-name "ssh" nil nil "AWS2" nil nil nil)
  nil))

AWS2 is a Host defined in ~/.ssh/config, with other settings (User, Identityfile, Port, etc).

More info:

• I have tried tramp-cleanup-*-connections (all variants thereof).
• Tried instead using the sshx: command/prefix - same error.
• I can open a plain bash terminal and successfully connect using ssh AWS2.
• In other IDEs, I am also able to set up an ssh-based SFTP connection and that works fine.
• I have set a simple prompt on the remote machine for "dumb" $TERM values.
• Tramp version: 2.3.5.26.3
• Emacs version: GNU Emacs 26.3 (build 2, x86_64-pc-linux-gnu, GTK+ Version 3.18.9) of 2019-12-23
• OS: Ubuntu 16.04
• Restarted my machine
• Looked for any clues that Tramp has been blocked on the remote machine (given other connection routes work), but didn't find anything.