Look, things like this will get your head boiling (I know that from experience), just forget why it happened, what is important is that you know you have been targeted.
The most probable explanation is that a service where you used this password was hacked, and your password’s hash was leaked in the dark web, which is why it wasn’t shown in haveibeenpwned yet.
A similar thing happened to me on multiple services and this is when I decided to go to the extreme and beef up my security in a way even If I was interrogated they won’t access a single account.
DISCLAIMER, this is extreme IMO, and it will take several weeks to do if you have hundreds of accounts like me.
You need to go into each account you have, change the password into a random 64 character password, remove your phone number, and setup 2FA that is using an authenticator app or a security key only.
1- Buy a security key called ONLYKEY, it’s like a Yubikey, but it allows you to protect it with a password, store 24 credentials, a self-destruct code (for your enemy if they ask) and store a Yubikey (if you have and existing one) to simulate its code creation.
Set it up, and create a Super complex master password (something like this h&#I49P2A#!QZ^s5K1rq363X@q^v8$*QOR34vGocDJC^Z) and store your master password on that key only.
2- Get Bitwarden password manager, and migrate all of your accounts onto there, and delete any credentials from your browser or any other password managers (LastPass is shit, and it was hacked multiple times before).
Use your ONLYKEY to add your master password, setup 2FA for your Bitwarden account and your other accounts.
3- Create a new email, use a service called SimpleLogin and change the email of each service you have to a new pseudo email, which you should encrypt with a PGP key, then redirect all your emails to the newly created email, that way even if you use Gmail, only you can read your emails since all the emails are encrypted, and each service will have only that pseudo email address if they are breached, your main email is secure. (SimpleLogin is also open-sourced)
If you do this, then your master password for your password manager will be 100% secure because even you won’t know it, your accounts will be secured because Bitwarden not only open-sourced, never been hacked, but also uses an advanced encryption technique (AES-CBC 256-bit with PBKDF2 SHA-256) which makes it impossible to anyone other than yourself to see your accounts credentials (zero trust model).
Bitwarden uses a method of autofill which prevents keylogging and your passwords won’t be stored in the clipboard when autofilling.
I store all of my banking details, my identities, my cards, and my 500 accounts in this technique since 2018, I check for breaches regularly (on the dark web as well) and none of my accounts were compromised ever since.
Like I said, it is a super complex procedure, it takes weeks to do, and it will force you to carry your ONLYKEY with you (or your phone with Bitwarden using biometrics on it) all the time.
If you are up for it give it a go, but you can’t half-ass it, you have to do everything, or it won’t give you the piece of mind that you want.