Eso es muy raro... bueno, no conozco mucho la distribución Fedora, pero en otras, CGI está instalado de base. Y aunque quisiera instalarlo, no me pediría instalar FastCGI. O al menos, me lo mostraría como una posible opción de mejora.
Eso sí... si ha desaparecido el CGI.pm del sistema, para mí eso ya no es ni un sistema viable ni fiable (ni confiable).
Puedes intentar una búsqueda en profundidad, para buscar por CGI.pm:
find / -name 'CGI.pm'