Is this a recommended approach? I would have thought that each user would generate their own key pair, and each user would have an account on the VM with their public key. That way users are authenticated using individual accounts and security, auditing applies to individual users.
You could create different ssh keys for your users.
ssh-keygen -t rsa -b 2048 Save the private key in your local and store public key in your user's ~/.ssh/authorized_keys. More information please refer to this official document.
Is there a way to do this with Linux VMs in Azure, where we wouldn't have to provision local accounts on each VM?
Yes, it is possible. But by default, linux does not support AD Authentication, you need install the module, please refer to this link. If you want Azure AD user to login, this link maybe helpful.