There was a time where Bitcoins transactions were thought to be super private
No there wasn't. Bitcoin has never been anonymous.
One can actually trace the address and if a person uses the same address a lot of times it is really not hard at all to connect it to an identity because of the KYC that now every wallet needs .
Every wallet? What are you talking about? If your wallet requires you to complete KYC, then you are either using the worst-of-the-worst (and probably a scam), or you are not using a wallet at all. The only thing that requires KYC is an account on a centralized exchange, which is categorically
not a wallet, and if you are storing your coins there long-term then you at high risk of losing them all. Any good hardware wallet, software wallet, paper wallet, mobile app, etc., does not require KYC or even an email address to use.
Further, any good hardware or software wallet will automatically generate a new address for each receiving transaction and a new address for each change output to prevent address reuse. If your wallet doesn't do this, again, you should change wallet.
The main thing is to choose a good wallet, and there will be no problems with security and anonymity
I have been using CoinsBank for 3 years, and there has been no reason to regret my choice so far