The ssh public keys of users are retrieved from a NFS share /public/keys using in sshd_config:
The OpenSSH in Ubuntu saucy supports a new command AuthorizedKeysCommand which would let us retrieve the public keys directly from LDAP.
AuthorizedKeysCommand "/usr/libexec/openssh/ssh-pubkey-helper -s %u"
We can't really deploy that on our labs instance right now since they are using Precise. So I am logging this bug for later on.