I just recently had to solve this problem. I ended up using this Python package: https://github.com/jirutka/ssh-ldap-pubkey
Does this support multiple sshPublicKey attributes or just one per user?
Any performance issues with constantly hitting LDAP?
I haven't seen performance issues, but it's a relatively small deployment in the scheme of things. There are also existing solutions for caching here. NSCD seems to be the go-to for caching LDAP query results directly. Alternately, you could cache credentials at the PAM level with pam-ccreds (Debian package name).