There are many things you can do.
First off, you can try compressing the data, which might and probably will help in many situations.
Another thing that might help is using chunks - dividing the map into smaller pieces (16x16, 32x32 or whatever you find to work best for you).
You can either use multiple files for this and load only the chunks that you need(or load them in order if you need all of them but not immediately) or, if your map is fixed in size, save them uncompressed in one big file with an index telling you which chunks are where and otherwise doing it the same as with multi-file solution.
Chunks have an additional advantage of not having to rewrite everything every time you modify something - just open the relevant file(s) or seek and write data at given locations in the file.
You should also investigate your loading/saving code because loading something that took seconds to save shouldn't be taking minutes. A good first guess would be to make sure you're not resizing an array thousands of times - if that's the case then either preallocate it or use a list and then convert it to an array.
Hope this helps.