Kira,
It's hard to comment on your interrupt latency time, as all sorts of things will affect the time taken, clock frequency, version of processor, what memory your code is running from, the priority of the interrupt etc.
Your time sounds quite long we have measured latency at between 81-83 cycles on a 1S10 full design which uses Nios II/f processor.
Chapter 6 of the Nios II Software Developer's Guide has some documentation on Exceptions and tips on how to reduce interrupt latency
Some things you could do to speed up your IRQ latency include:
Use the highest priority interrupt available
Place your interrupt handler into an on chip memory