Passwords in data leak scam on Safari

The warning is legitimate. Read about it here: Password Monitoring - Apple Support. It has nothing to do with how new or old your Mac happens to be.

However... you don't have to act upon it. Furthermore, if you decide to change your password I would not click the blue button in that dialog for the reasons you experienced:

... I clicked change password and it took me to a website that had the same logo as the one I was on before but it hadn't loaded properly and it said not secure in the search bar so immediately closed the tab.

Good decision. Navigate on your own to the website in question, and change it there.

Apple's documentation on the subject is intentionally vague, but it does make reference to the fact it performs those checks at "...an interval that's independent of the user's passwords or their password manager usage patterns."

I have encountered it on an iPhone so it's not strictly limited to Macs. Also, if you dismiss the dialog by clicking "Not Now" it won't harass you again, for at least a little while.

You're welcome. I did some experimenting and eventually made that warning appear on an iPhone. The corresponding "Change password on website" merely opened the website in question. In my case it happened to be the correct website, but it did not prompt for any specific action. As such clicking the "Change Password" button did not seem very helpful to me. All the more reason to navigate to the website on your own and take action from there (if you want to).