What tier is your database running at? Your database may be the bottleneck. I'd suggest temporarily scaling up your database tier to something very high to perform that import, then scale it back down after your import is complete.
If you have segments that run automatically or on a scheduled basis, that processing will run as needed when those contacts are imported so there could be some additional processing that's happening in the background that could be causing the slowness.