It is no surprise that anonymity has been leaving bitcoin. Bitcoin is not as anonymous as it used to be.
When was the time that bitcoin was completely anonymous? You have an exact address and yes, nobody knows who does it belong to, but it's no secret that transactions aren't anonymous, so every address can be tracked and if you link it to something else - you're not anonymous anymore. As it was planned - for each transaction you should use new address, this would enhance your anonymity, but even such transactions can be tracked.
Then I suggest you using any service like the Chipmixer or the bitblender. They are quite effective in breaking the trail of the bitcoin transactions and increase your anonymity.
Yes, that seems like a good decision. But how do you know you can trust them? In my understanding of how it works you kind of send your money and the address, where you want your money to be delivered and then website workers do that for you? How do you know they won't mistake, or just take your money. Or, in case it isn't done manually, there's still another problem: how can you be sure that you transaction story isn't kept? I know I'm being paranoid, but seriously, how do they prove it?