The evolution of the Fermi surface of CeRh$_{1-x}$Co$_x$In$_5$ was studied as a function of Co concentration $x$ via measurements of the de Haas-van Alphen effect. By measuring the angular dependence of quantum oscillation frequencies, we identify a Fermi surface sheet with $f$-electron character which undergoes an abrupt change in topology as $x$ is varied. Surprisingly, this reconstruction does not occur at the quantum critical concentration $x_c$, where antiferromagnetism is suppressed to T=0. Instead we establish that this sudden change occurs well below $x_c$, at the concentration x ~ 0.4 where long range magnetic order alters its character and superconductivity appears. Across all concentrations, the cyclotron effective mass of this sheet does not diverge, suggesting that critical behavior is not exhibited equally on all parts of the Fermi surface.