Users aren’t allowed to reuse old passwords for security reasons. How to alleviate this pain point?

I work at a healthcare tech start up which is pretty strict about its login guidelines, largely because protecting patient and provider info is such a vital need in this industry. But while our strictness serves an important need, it can cause a fair amount of headaches for our providers. The source of much of this frustration is the fact that providers, when changing their passwords, are not allowed to reuse any of their last 12 passwords. And they're having difficulty remembering their old passwords, and there's no secure/systematic way of providing that info to them. What's worse is that they're also required to change their passwords every 90 days. So between the cognitive load required to remember all of their recent passwords and the frequency with which they need to update their passwords, providers are getting fed up, and are either abandoning the platform in frustration or relying heavily on customer support, who are inundated with requests to change providers' passwords for them.

That said, does anyone have any experience with the "previous password" problem? And if so, what approaches have you used to mitigate it? Thanks for your help!

(and an FYI, I asked my security team if there was any wiggle room on the frequency of the pw change, as well as the change criteria, but they said its pretty much set in stone)