In the movies, the Agents seem to spend most of their time in the Matrix. The cops are even familiar with them, and they get around the city by car, but where do they go when their human shell gets murdered?
When they're killed, Agents present themselves for inspection by the Machine Mainframe. If they're found to be working effectively, they're returned to the Matrix and decanted back into the nearest useful "shell". If they're ineffective, they're either destroyed or upgraded.
... you destroyed me, Mr. Anderson. Afterward, I knew the rules, I understood what I was supposed to do, but I didn't. I couldn't. I was compelled to stay. Compelled to disobey.
When they're not actively fighting with Zionese rebels, we see a number of Agents in Animatrix: Beyond monitoring the state of the Matrix, looking for bugs and glitches and in Animatrix: World Record keeping an eye on those who look like they're potentially going to 'wake up' through sheer exertion.
Agents are programs, when they are not in a shell they do not actually go anywhere they are programs that are running in the background of the matrix OS