@Dimiter @Anastasia - Here is an example failure from a test run where I removed the '--config agent-stream=devel' again, and added '--debug' and '-v' to the juju ssh invocations:

+ juju --debug ssh nova-compute/0 -v 'sudo service nova-api-metadata restart'
14:32:38 INFO  juju.cmd supercommand.go:63 running juju [2.0.0 gc go1.6.2]
14:32:38 DEBUG juju.cmd supercommand.go:64   args: []string{"juju", "--debug", "ssh", "nova-compute/0", "-v", "sudo service nova-api-metadata restart"}
14:32:38 INFO  juju.juju api.go:72 connecting to API addresses: [104.198.70.102:17070 10.240.0.35:17070]
14:32:38 INFO  juju.api apiclient.go:519 dialing "wss://104.198.70.102:17070/model/fedec934-9bd8-4a2d-83dc-c24426e4621e/api"
14:32:38 INFO  juju.api apiclient.go:309 connection established to "wss://104.198.70.102:17070/model/fedec934-9bd8-4a2d-83dc-c24426e4621e/api"
14:32:38 DEBUG juju.juju api.go:263 API hostnames unchanged - not resolving
14:32:38 DEBUG juju.cmd.juju.commands ssh_common.go:226 proxy-ssh is false
14:32:38 DEBUG juju.utils.ssh ssh.go:292 using OpenSSH ssh client
OpenSSH_7.2p2 Ubuntu-4ubuntu1, OpenSSL 1.0.2g-fips  1 Mar 2016
debug1: Reading configuration data /home/ubuntu/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to 104.154.32.63 [104.154.32.63] port 22.
debug1: Connection established.
debug1: identity file /home/ubuntu/.local/share/juju/ssh/juju_id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/ubuntu/.local/share/juju/ssh/juju_id_rsa-cert type -1
debug1: identity file /home/ubuntu/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/ubuntu/.ssh/id_rsa-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.2p2 Ubuntu-4ubuntu1
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.2p2 Ubuntu-4ubuntu2.1
debug1: match: OpenSSH_7.2p2 Ubuntu-4ubuntu2.1 pat OpenSSH* compat 0x04000000
debug1: Authenticating to 104.154.32.63:22 as 'ubuntu'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: <email address hidden>
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: <email address hidden> MAC: <implicit> compression: none
debug1: kex: client->server cipher: <email address hidden> MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY

debug1: Server host key: ecdsa-sha2-nistp256 SHA256:AfXRezEW5wJ2IEHCQRsmjVWesrtc4QfW6NzwbIM1Kc0
debug1: Host '104.154.32.63' is known and matches the ECDSA host key.
debug1: Found key in /tmp/ssh_known_hosts849103164:3
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<rsa-sha2-256,rsa-sha2-512>
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/ubuntu/.local/share/juju/ssh/juju_id_rsa
debug1: Authentications that can continue: publickey
debug1: Offering RSA public key: /home/ubuntu/.ssh/id_rsa
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).
14:32:38 DEBUG juju.api monitor.go:35 RPC connection died
14:32:38 INFO  cmd supercommand.go:465 command finished