Hello,
Using EEPROM for storage of 77 bytes of NV data will require that twenty sectors, each of 4 bytes, be erased. Since the erase of each sector will require a period of 20 - 27 milliseconds, the total period for 20 sectors should be 400 - 540 milliseconds, which is comparable to what you have observed.
If you were to use a flash sector, rather than EEPROM, only a single 512 byte sector would need to be erased, for a total erase period of 20 - 27 milliseconds. However, this also exceeds the available time, so the sector would still need to be pre-erased.
Regards,
Mac