Faits : A. En 2002, C.X._, ressortissant kosovar, a été naturalisé suisse à la suite de son mariage avec une Suissesse, laquelle est décédée en août 2015. Alors qu'il était marié avec son épouse suisse, il a reconnu, en 2013, quatre enfants nés entre 2001 et 2010, issus de son union (coutumière) avec une ressortissante kosovare. En 2015, C.X._ a déposé une demande de naturalisation facilitée pour ses fils, A.X._, né en 2002, et B.X._, né en 2005. Le Service des affaires institutionnelles, des naturalisations et de l'état civil de l'Etat de Fribourg (ci-après : le Service des affaires institutionnelles) a émis un préavis négatif, soulignant que le père des prénommés avait obtenu abusivement la nationalité helvétique. Par décisions datées du 29 septembre 2016, le Secrétariat d'Etat aux migrations (ci-après : le SEM) a accordé la naturalisation facilitée aux prénommés en vertu de l'art. 58c de l'ancienne loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (ci-après : aLN; RO 1952 1115 et RO 2005 5233) intitulé « naturalisation facilitée des enfants de père suisse ». Il a joint à l'égard du Service des affaires institutionnelles du canton de Fribourg une lettre l'informant qu'il ne pouvait rien entreprendre pour annuler la naturalisation abusive du père des prénommés, le délai de prescription étant écoulé. B. Le Service des affaires institutionnelles du canton de Fribourg a recouru contre les décisions du 29 septembre 2016 auprès du Tribunal administratif fédéral. Par arrêt du 9 mai 2018, celui-ci a admis les recours et annulé les décisions du SEM. C. Agissant par la voie du recours en matière de droit public, A.X._ et B.X._, représentés par leur père, demandent principalement au Tribunal fédéral d'annuler l'arrêt du 9 mai 2018 et de leur octroyer la naturalisation facilitée. Ils concluent subsidiairement au renvoi de la cause au SEM pour nouvelle décision au sens des considérants, après instruction complémentaire relative à leur intégration. A titre encore plus subsidiaire, ils requièrent le renvoi de la cause au Tribunal administratif fédéral pour nouvelle décision au sens des considérants. Invités à se déterminer, le Service des affaires institutionnelles du canton de Fribourg et le Tribunal administratif fédéral concluent au rejet du recours. Le SEM a déposé des déterminations. Les recourants ont répliqué par courrier du 10 septembre 2018.