How come nobody replied to this. I have the exact same problem to the point of the clone stamp being useless. The problem hasn't been helped by upgrading to CC2020. Other tools also lag, but the clone is by far the worst.
I solved the lagging of clone stamp and healing brush by going into the Clone Source tab and unchecking "Show Overlay". This problem was not present in CC2018, but something in CC2019 changed, and anything requiring a sampled source became laggy and frustrating - unusable. This seems to fix it completely, both tools are back to their old snappy self. Heads up, Adobe engineers!