I think the current system is sort of okay, just for being in keeping with the rest of the character system. But regarding spying it could use some tweaks to hasten the appearance of new agents.
One option I could think of would be to spend money directly, either to purchase a new agent or get a heightend chance of one appearing after a time. Maybe spies acquired through this route should usually be far less powerful than the random chance, 'elite' persons.
A far more interesting possibility could be in the use of an existing spy. Create a new mission, 'recruit agents', 'build network' or whatever'd be a good name for that activity. When successful, a new agent should appear. Chances of success could be determined by length of the mission (the usual month, quarter year or whole year), skill of the recruiting agent, number of agents you already have and race traits (with Ketarov, etc having an advantage).
The risk of the mission would be very low to non-exitent, at least for the recruiting agent. But you could run a risk of getting a double-agent into your service. Just keep in mind that the recruiter isn't available for counter intelligence, so there is a trade-off as there should be with every agent activity.