linux_config = LinuxConfigurationSet(vm_name, 'xxxx', 'yyyyy', True)

SERVICE_CERT_THUMBPRINT = "1058XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
linux_config.ssh = SSH()
pair = KeyPair(SERVICE_CERT_THUMBPRINT, '/home/xxxx/temp/mycert.pub')
linux_config.ssh.key_pairs.key_pairs.append(pair)

sms.create_virtual_machine_deployment(service_name=hosted_service_name,
    deployment_name=hosted_service_name,
    deployment_slot='production',
    label=hosted_service_name,
    role_name=hosted_service_name,
    system_config=linux_config,
    os_virtual_hard_disk=os_hd,
    role_size='Small')

OpenSSH_6.6.1, OpenSSL 1.0.1f 6 Jan 2014
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to dw9y1qzwp2.cloudapp.net [104.208.26.98] port 22.
debug1: Connection established.
debug1: identity file mycert.key type -1
debug1: identity file mycert.key-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.6.1p1 Ubuntu-2ubuntu2.3
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.6p1 Ubuntu-2
debug1: match: OpenSSH_6.6p1 Ubuntu-2 pat OpenSSH_6.5*,OpenSSH_6.6* compat 0x14000000
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5-etm@openssh.com none
debug1: kex: client->server aes128-ctr hmac-md5-etm@openssh.com none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA a2:80:7e:dc:b6:47:c5:d7:97:0a:7b:9c:75:c6:1f:85
debug1: Host 'dw9y1qzwp2.cloudapp.net' is known and matches the ECDSA host key.
debug1: Found key in /home/rohan/.ssh/known_hosts:22
debug1: ssh_ecdsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: xxxx@gmail.com
debug1: Authentications that can continue: publickey
debug1: Trying private key: mycert.key
debug1: key_parse_private2: missing begin marker
debug1: read PEM private key done: type RSA
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).