Right - so you have 5 fans to monitor. that's an important information

So 3 answers:
Software solution: do use change interrupt. you need to understand that you won't get differentiated ISR for each pin, if there is a change on any of the pins in a group, then the ISR will fire.
--> can you let us know which Arduino you use?
Try to group them on the same PORT and in the ISR code do read the PORT (that's fast and reads all of them in one go) and check what bits have changed from last read => you'll know which fan sent a RISING or FALLING signal and modify the appropriate counter accordingly. that could be multiple changes at the same time.
Hardware + Software:
using a Programmable Interrupt Controller. A programmable interrupt controller is used to combine several sources of interrupt onto one or more CPU lines, allowing priority levels to be assigned to its interrupt outputs. The Intel 82C59A is pretty simple to use.
Look at an General Purpose parallel Input/Output (GPIO) expanders like the MCP23017 or MCP23008 for which interrupts can be configured to be edge or level-sensitive for each input and offer SPI or I2C versions -- or those from Semtech (the SX1501-SX1506 family).