Using SourceSafe over VPN is painfully slow. There is nothing you can do about the speed. It will stay slow if you access it with the LAN mode. But there is a solution that will help SourceSafe to be a little faster. You need to use Remote Web Access over Http. The time to check-in a single file in my case, has gone from 1 minute to 5 seconds.

Here is some link that will help  you setup your environment:

How to: Enable the Internet Service for Remote Access

Alin Constantin : Installing and configuring Microsoft Visual SourceSafe for Internet (Remote) access