Very simple - just stop giving them to people and let them be forgotten as a concept.
> Do you suggest that we fundamentally overturn how our entire society works just to remove cheating?
Are you suggesting that university diplomas are a fundamental factor of how our society works? If so, would you please explain how?
> First of all, which of these are you saying should be "removed"? Only the ones from universities? All of them?
Only those from the universities. Universities are officially recognized "places to learn" and they should be kept that way. Studying for longer than "appropriate" number of years should not be frowned upon, but encouraged. The whole process of "verification" should be completely independent of learning.
Bundling "learning" and "verification", the way universities do, inevitably leads to hordes of people who want verification, but not learning - i.e. cheaters.
> Secondly, how do you remove them? Do you outlaw them?
Very simple - stop issuing them (I suppose a country-level ban of university diplomas could do, but politics depend on the country so I can't give you a general answer). If you want a certificate authority, make a certificate authority and make it its sole purpose to verify that people have the knowledge. Leave university out of that.
> Thirdly, what happens when they're all gone? How do you certify a surgeon?
A certificate authority (that only verifies surgeons' skills, and doesn't bundle the process with "learning").