Governmental record keeping of this sort is literally one of the first uses for computers.
Example... oh, there's lots of people with TS clearances in this little town in the midwest. Maybe there's something to that. Let's check it out.
One centralized location that you can phone in with some smart authentication system, human workers for the rest of it. Getting cleared already takes a while (weeks or longer) so what's the huge problem with keeping the classified stuff actually safe?
At this point I don't feel especially confident that any of this stuff is going to stay secure given the prevalence of leakers and hacks. The choice is store on a computer and accept that it is going to be leaked at least occasionally or do not store it on a computer.
If the OPM computers currently average 1 query per second (a number I'm pulling out of thin air, but one I'd guess was conservative). Even if you restrict that to 8X5 business hours access (an efficiency loss in itself) you have 2400 phone calls to answer and then traverse of the gigantic document store we created above.
I think this is one of those cases where people have very bad intuitive understanding of the scale of the data and what dealing with this kind of data looks like in a physical form.