Antrix:
I believe the hardware is configured correctly, please advice if otherwise.
Nope. The Arduino is a 5V device, and the GPS is a 3.3V device. You should not connect the Arduino transmit pin 4 directly to the GPS RX pin. Here is a post that describes several alternatives, with level shifting modules or discreet parts (resistors and a diode).
I would strongly suggest using AltSoftSerial on pins 8 & 9 for the GPS. SoftwareSerial is very inefficient, because it disables interrupts for long periods of time. This will interfere with other parts of your sketch, like updating the OLED.
If you can't use those pins, you should use my NeoSWSerial. It is almost as efficient as AltSoftSerial, and it can use any two pins.
And yes, you can hook the GPS TX pin to the Arduino RX pin 0. You can still do debug prints to the Serial Monitor, but you would have to disconnect the GPS TX wire if you upload over USB. That would be most efficient.
I would also suggest my NeoGPS library. It is smaller, faster and more accurate than all other libraries. It groups all those sentences into one coherent fix data structure, exactly once per second. This avoids the messy IsUpdated tests, and updates the OLED just when the GPS goes quiet for a while. This probably has the greatest impact on the performance, especially if you use a software serial port. As you noticed:
Seems like its the code code that dumps too much data. That is all I could think of.
Yes, many example programs from other libraries have this problem: printing too much at the wrong time.
And you are using the outdated U8glib. I would strongly suggest switching to the new U8G2lib.
I have attached a NeoGPS+NeoSWSerial+U8g2 version of your sketch. Notes:
* The correct way to perform timezone shifts is to convert the DDMMYY-HHMMS to a seconds count from a time "origin" (aka EPOCH). Then add the timezone shift, in seconds) and convert it back to a DDMMYY-HHMMYY structure. The code above shows how to set the localTime structure from the GPS time plus a seconds offset. This will produce the correct day, month and year, even if the time offset crosses one of those boundaries.
* Remember that a GPS device may not know all the pieces of a fix, yet. If it does not have a valid speed, it will send an empty field to the Arduino. NeoGPS marks each piece with a valid flag, so your code can handle cases when a piece is really not available.
* All double-quoted string arguments are using the F macro to save RAM.
* I'm not certain of the correct u8g2 constructor:
U8G2_SSD1306_128X64_NONAME_1_HW_I2C u8g2( U8G2_R0, U8X8_PIN_NONE ); // no rotation
... nor which of the new fonts you should use:
u8g2.setFont(u8g2_font_inr21mr); // instead of profont22r?
* Be sure to review the OLED_RESET pin number. It looks like you were using the same pin for SoftwareSerial. 
* The attached sketch is significantly smaller:
The original sketch uses 25832 bytes of program space and 1085 bytes of RAM.
The NeoGPS version uses 20282 bytes of program space and 1042 bytes of RAM.
Some of the savings could be due to the fonts.
PaulS:
static const int RXPin = 4, TXPin = 3;Do you know what the static keyword does? At global scope?
Hmm... Do you know what it does? There is absolutely nothing wrong with the usage here, as it will reduce name collisions. This name is not very unique, so I might even suggest it here. I would definitely suggest it for a routine called "draw". It's a good coding habit to have, although it seems the OP did not know it was a good thing to do...
@Antrix, it means that the variable name "RXPin" is visible only within this file. If another file, perhaps in a library, had also declared the same variable name (of the same "const int" type), you would have gotten a "multiply-defined symbol" link error.
If you want to try it, NeoGPS is available from the Arduino IDE Library Manager, under the menu Sketch -> Include Library -> Manage Libraries. Even if you don't try it, be sure to read the Troubleshooting page for other tips for GPS sketches.
Cheers,
/dev
P.S. You will have to enable the following items in GPSfix_cfg.h:
#define GPS_FIX_HDOP
#define GPS_FIX_VDOP
#define GPS_FIX_PDOP
#define GPS_FIX_LAT_ERR
... and the following items in NMEAGPS_cfg.h:
#define NMEAGPS_PARSE_GSA
#define NMEAGPS_PARSE_GST
Antrix.ino (5.31 KB)