The problem is often embedded in the processes and many times the new people fall into the same errors.
Well that's certainly a possibility, but if you do that enough times, you'll eventually get a new group of people with enough clue to look for the flaws in the processes, rather than continuing to do things the way they've always done things. The critical part is to replace more than just the top couple of layers of management. The farther down you go, the more likely you are to result in changes to the actual day-to-day processes. You probably don't have to change the bottom-tier of management, but you do have to make it clear to the second tier that they should be regularly asking the bottom tier for updates on changes to their processes, and if nothing is happening, give them the authority to change the bottom tier selectively.
I would argue a better model would be to split them up into several different agencies with more narrowly focused missions.
The problem is, that's what we had before, and then 9/11 happened, and everyone knee-jerked and said, "Why didn't you stop this?" and the answer was because things were so compartmentalized that the different agencies didn't talk to each other.
No, what's needed is to A. show them right from wrong, and B. establish clear oversight. Ideally, the second step would be to have parts of each spy agency working against one another, trying to dig up dirt on the others, to keep them from becoming complacent and bending the law when they see fit.