It is possible to use Teleport in agentless mode - it requires Teleport to be deployed in what we call “recording proxy mode” - where sessions are MITM-ed and recorded on the proxy rather than the default where Teleport records on the nodes. It also requires SSH agent forwarding to be enabled (which is the default with Teleport)
Please see this section of the documentation: https://gravitational.com/teleport/docs/admin-guide/#recording-proxy-mode
In terms of devices behind NAT, if you’re saying that you’d use your cloud VM as a bastion server and then SSH to
sshd nodes from there (or use it via
ProxyCommand then that would work. Otherwise, Teleport would require an agent installed on the nodes to create a reverse tunnel from the node back to the Teleport server.
Feel free to post again if you have questions!