Faits :
A.
A.a. Par ordonnance du 22 décembre 2009 (ROF 2009_148; ci-après l'ordonnance du Conseil d'Etat), entrée en vigueur au 1 er janvier 2010, le Conseil d'Etat du canton de Fribourg a modifié le règlement cantonal du 17 décembre 2002 du personnel de l'Etat (RPers-FR; RSF 122.70.11) s'agissant des prescriptions sur le travail de nuit et le service de garde. Selon son auteur, ces modifications avaient pour but de rendre conforme la législation cantonale en ce domaine à la loi fédérale du 13 mars 1964 sur le travail dans l'industrie, l'artisanat et le commerce (LTr; RS 822.11), laquelle instaurait depuis 2000 et 2003 une compensation intégrale du service de garde, ainsi qu'une compensation en argent, respectivement en temps, en fonction du nombre de nuits effectuées.
Dans le préambule de cette ordonnance, il était indiqué que les nouvelles dispositions ne déploieraient leurs effets que progressivement sur les prochaines années. La FEDE (Fédération des associations du personnel du service public du canton de Fribourg), avec laquelle des discussions au sujet de la prise en compte du travail de nuit avaient été menées, s'était déclarée d'accord sur les décisions du Conseil d'Etat y relatives, notamment sur l'entrée en vigueur progressive dès 2010, sans effet rétroactif.
A.b. A._ travaille en qualité d'infirmier auprès du Réseau fribourgeois de santé mentale (ci-après: RFSM). Dans son travail, il a été amené à travailler de nuit. Le 28 juillet 2010, il s'est adressé au RFSM en faisant valoir que la compensation de son travail n'était pas conforme à la LTr et que celle-ci devait s'appliquer pour la période antérieure au 1 er janvier 2010. Il réclamait à ce titre la compensation de 841 nuits, soit 5887 heures de travail, par un repos de 10 % pour les années 2005 à 2009. Par décision du 18 février 2013, le RFSM a rejeté sa demande.
Le recours formé par le prénommé devant le Conseil d'Etat contre le prononcé du 18 février 2013 a été rejeté par décision du 27 mai 2015.
Le 29 juin 2015, A._ a recouru devant le Tribunal cantonal de l'Etat de Fribourg (I re Cour administrative), concluant à ce que le RFSM soit condamné à lui accorder la compensation en temps de repos de 588.7 heures (compensation du travail de nuit pour les années 2005 à 2009). Statuant par arrêt du 23 mai 2017, le Tribunal cantonal a rejeté ce recours.
A.c. A._ a formé un recours constitutionnel subsidiaire contre cet arrêt. Statuant le 19 juin 2018, le Tribunal fédéral a retenu que la motivation de l'autorité judiciaire cantonale apparaissait à ce point inédite, voire surprenante, qu'elle eût nécessité une interpellation spécifique des parties pour empêcher une violation de leur droit d'être entendues. Le Tribunal fédéral a annulé le jugement précité et renvoyé la cause à l'instance cantonale pour nouvelle décision (arrêt 8C_484/2017, 8D_3/2017 du 19 juin 2018).
B.
Après avoir invité le prénommé à se déterminer, la cour cantonale a statué à nouveau par arrêt du 28 novembre 2018, rejetant le recours.
C.
A._ interjette un recours constitutionnel subsidiaire contre ledit arrêt. Il conclut, sous suite de frais et dépens, à son annulation et au renvoi de la cause à l'instance cantonale pour qu'elle statue sur le fond de ses prétentions telles qu'elles figurent dans son recours du 29 juin 2015.
Le RFSM conclut principalement à l'irrecevabilité du recours, subsidiairement à son rejet.
La cour cantonale a renoncé à se déterminer.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 282; <ref-ruling> consid. 1.1 p. 197).
2.
2.1. Selon l'art. 2 de la loi du 17 octobre 2001 sur le personnel de l'Etat (LPers; RSR 122.70.1), cette loi s'applique aux personnes qui exercent une activité au service de l'Etat et qui sont rémunérées pour cette activité (al. 1); sont considérés comme exerçant une activité au service de l'Etat les collaborateurs et collaboratrices de l'administration cantonale - y compris des établissements personnalisés de l'Etat -, du Secrétariat du Grand Conseil et de l'ordre judiciaire (al. 2). Le personnel du RFSM fait partie des établissements personnalisés visés à l'art. 2 al. 2 LPers (art. 2 al. 1 let. h du règlement du personnel de l'Etat [RPers; RSF 122.70.11]). Le jugement entrepris a donc été rendu en matière de rapports de travail de droit public au sens de l'art. 83 let. g LTF.
2.2. La décision attaquée porte sur des compensations, en temps de repos, de prestations de travail de nuit. La prétention du recourant à ces compensations se fonde sur l'art. 22 LTr qui interdit le remplacement du temps de repos par d'autres prestations. La décision entreprise concerne donc une contestation non pécuniaire, de sorte que l'exception prévue à l'art. 83 let. g LTF s'applique. Par conséquent, seule la voie du recours constitutionnel subsidiaire - choisie par le recourant - peut entrer en considération.
3.
La qualité pour former un recours constitutionnel subsidiaire suppose un intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>). Les intérêts que le recourant invoque doivent être protégés soit par une règle du droit fédéral ou du droit cantonal, soit directement par un droit fondamental spécifique (<ref-ruling> consid. 1.2 p. 326; 229 consid. 3.2 p. 235), par opposition à des droits constitutionnels non spécifiques, telle que l'interdiction de l'arbitraire, qui ne peut être invoquée que si les normes visées accordent à l'intéressé un droit ou servent à protéger ses intérêts prétendument lésés. Autrement dit, le recourant doit se trouver dans la sphère de protection de la disposition dont il critique l'application arbitraire (<ref-ruling> consid. 5.3.3. p. 247 et les références; <ref-ruling> consid. 1.3 p. 308). Il incombe à la partie recourante d'alléguer les faits qu'elle considère comme propres à fonder sa qualité pour recourir au Tribunal fédéral lorsqu'ils ne ressortent pas à l'évidence de la décision attaquée ou du dossier de la cause (<ref-ruling> consid. 1.1 p. 4; <ref-ruling> consid. 1.2 p. 539). Par ailleurs, l'intérêt juridique au recours doit en principe être actuel. L'intérêt doit être actuel non seulement au moment du dépôt du recours, mais encore au moment où l'arrêt est rendu (<ref-ruling> consid. 1.1 p. 103; arrêt 8C_767/2016 du 7 août 2017 consid. 5.1.2). En outre, indépendamment du point de savoir si le recourant est légitimé sous l'angle de l'<ref-law> à remettre en cause une décision sur le fond, il peut faire valoir la violation de ses droits de partie équivalant à un déni de justice formel. Mais il ne doit alors pas invoquer par ce biais, même indirectement, des moyens qui ne peuvent être séparés du fond. Seuls les griefs de nature formelle qui sont séparés de l'examen de la cause au fond peuvent donc être présentés. En revanche, les griefs qui reviennent de facto à critiquer l'arrêt attaqué sur le plan matériel sont exclus (<ref-ruling> précité consid. 1.2 p. 326 et les arrêts cités).
4.
4.1. Le recourant se plaint d'une application arbitraire du droit cantonal (art. 9 Cst.), reprochant aux juges précédents d'avoir considéré, de façon insoutenable, que le préambule de l'ordonnance du Conseil d'Etat du 22 décembre 2009 constituait une décision générale englobée dans un acte normatif déployant des effets concrets directement sur les droits du cercle des administrés concernés et n'ayant pas à être individualisée par une quelconque décision ultérieure. Selon la juridiction cantonale, le recourant aurait, par conséquent, dû contester ce préambule, en tant qu'il n'accordait aucun effet rétroactif à la modification du RPers-FR, selon la procédure applicable aux actes législatifs, ce qu'il n'a fait que tardivement en s'adressant à une autorité incompétente (cf. jugement attaqué, consid. 5.2). A._ conteste que la partie du préambule en question, qui dénie toute rétroactivité aux dispositions de l'ordonnance précitée, puisse être tenue pour une décision qui lui serait directement applicable, au regard des dispositions de l'art. 4 du Code de procédure et de juridiction administrative de l'Etat de Fribourg (CPJA-FR; RSF 150.1) et de la jurisprudence du Tribunal fédéral en matière de décisions générales (ou collectives) (cf. arrêt 8C_130/2014 du 22 janvier 2015 consid. 2.2.2, in SJ 2015 I p. 293). Par ailleurs, en invoquant l'art. 29 al. 1 Cst., le recourant se plaint d'un déni de justice formel dans la mesure où les juges cantonaux l'ont privé de la possibilité d'obtenir un contrôle concret de ses prétentions et droits en estimant qu'il aurait dû contester le préambule litigieux par la procédure applicable à la contestation des actes normatifs.
4.2. Le RFSM conteste la recevabilité du recours au motif que la disposition de droit cantonal (art. 4 CPJA-FR) dont le recourant soutient qu'elle a été appliquée arbitrairement ne lui confère aucun droit, ni ne vise à protéger ses intérêts prétendument lésés. En outre, selon l'intimé, le recourant se plaint d'un déni de justice qui ne peut être séparé du fond. Enfin, l'intimé allègue que A._ n'est plus employé du RFSM depuis un certain temps et que, par conséquent, il ne pourra plus faire valoir la compensation en temps de repos qu'il prétend et ne dispose plus d'un intérêt actuel à recourir.
4.3.
4.3.1. En l'espèce, la disposition de droit cantonal visée par le recours, à savoir l'art. 4 CPJA-FR définit la notion de décision administrative. De la sorte, elle n'accorde pas de droit à l'intéressé en matière de compensation de son travail de nuit. Ainsi, le recourant n'invoque aucune norme dont il pourrait déduire une position juridiquement protégée. Le seul fait qu'il a été débouté en procédure cantonale ne suffit pas pour créer un tel intérêt.
4.3.2. De plus, les griefs d'application arbitraire de cette disposition de droit cantonal et de déni de justice formel que le recourant adresse au jugement attaqué sont identiques, à mesure qu'ils s'en prennent tous deux à l'appréciation des premiers juges selon laquelle le RFSM, puis le Conseil d'Etat n'auraient pas dû entrer en matière sur la demande de prestations de l'intéressé, ni sur son recours. Or, ces griefs reviennent de facto à critiquer l'arrêt attaqué sur le plan matériel et sont donc exclus par le principe jurisprudentiel rappelé plus haut (cf. consid. 3 in fine). Il est dès lors douteux que le recours soit recevable sous l'angle de l'<ref-law>. La question peut cependant rester ouverte vu le sort à réserver au recours. Il en va de même en ce qui concerne l'intérêt actuel à recourir, mis en cause par l'intimé.
5.
Appelé à revoir l'application faite d'une norme cantonale sous l'angle de l'arbitraire, le Tribunal fédéral ne s'écarte de la solution retenue que si celle-ci apparaît insoutenable ou en contradiction manifeste avec la situation effective, ou encore si elle a été adoptée sans motifs objectifs et en violation d'un droit certain. En outre, il ne suffit pas que les motifs de la décision critiquée soient insoutenables, encore faut-il que cette dernière soit arbitraire dans son résultat (<ref-ruling> consid. 6.2 p. 239 et les références). Il ne suffit d'ailleurs pas non plus qu'une solution différente de celle retenue par l'autorité cantonale puisse être tenue pour également concevable ou apparaisse même préférable (<ref-ruling> consid. 2.1 p. 168; <ref-ruling> consid. 3.2.5 p. 339; <ref-ruling> consid. 4.2 p. 560).
6.
6.1. L'ordonnance du Conseil d'Etat a la teneur suivante:
"Considérant:
Actuellement, le travail accompli la nuit entre 20 heures et 6 heures fait l'objet de dispositions spécifiques qui octroient des indemnités pour cet inconvénient.
Or les établissements personnalisés de l'Etat peuvent être considérés comme étant soumis aux dispositions de la loi fédérale sur le travail (LTr) relatives à la durée du travail et du repos. Ainsi, pour les catégories de personnel leur étant rattachées, les dispositions spécifiques pour le travail de nuit, instituant une compensation en temps à raison de 110 % entre 23 heures et 6 heures, doivent être prévues en lieu et place des indemnités. Toutefois, pour tenir compte de la pénibilité des fonctions concernées, le Conseil d'Etat a décidé d'aller au-delà des exigences de la LTr, en cumulant la compensation en temps et l'octroi des indemnités.
En outre, la compensation en temps sera progressivement étendue entre 20 heures et 6 heures et atteindra 15 % pour les personnes de plus de 50 ans. Par égalité de traitement, ces dispositions seront également applicables à l'ensemble du personnel de l'Etat.
Par ailleurs, la compensation spécifique octroyée pour le travail de nuit et l'instauration généralisée, conformément à la LTr, de l'alternance du travail de jour et de nuit nécessitent que l'on engage du personnel supplémentaire et que l'on mette en place des mesures organisationnelles adéquates.
Ces nouvelles dispositions ne déploieront donc leurs effets que progressivement sur ces prochaines années. La FEDE, avec laquelle des discussions au sujet de la prise en compte du travail de nuit ont été menées, s'est déclarée d'accord sur les décisions du Conseil d'Etat y relatives, notamment sur l'entrée en vigueur progressive dès 2010, sans effet rétroactif.
Sur la proposition de la Direction des finances,
Arrête:
Art. 1
Le règlement du 17 décembre 2002 du personnel de l'Etat (RPers) (RSF 122. 70.11) est modifié comme il suit:
Art. 47 Travail de nuit ( art. 58 LPers)
1 Le collaborateur ou la collaboratrice dont la fonction l'exige et dont le cahier des charges le prévoit peut être tenu-e d'accomplir une partie de son horaire ordinaire de travail la nuit.
2 Est considéré comme travail de nuit le travail accompli entre 20 heures et 6 heures, l'article 47a al. 2 let. a restant réservé.
3 L'alternance entre travail de nuit et travail de jour est fixée en conformité avec les dispositions de la législation fédérale. Elle entre progressivement en vigueur, jusqu'au 1er janvier 2012 au plus tard.
4 Les prescriptions spéciales applicables à certaines catégories de personnel sont réservées.
Art. 47a (nouveau) Compensation du travail de nuit ( art. 58 LPers)
1 Le travail accompli la nuit est compensé:
a) à raison de 110 % jusqu'à la fin de l'année civile au cours de laquelle le personnel a 49 ans révolus;
b) à raison de 115 % dès le début de l'année civile au cours de laquelle le personnel a 50 ans révolus.
2 Toutefois, la compensation prescrite à l'alinéa 1 est progressivement octroyée, de la manière suivante:
a) dès le 1er janvier 2010, la compensation est de 110 % entre 23 heures et 6 heures;
b) dès le 1er janvier 2013, la compensation est, entre 20 heures et 6 heures, de 110 % jusqu'à la fin de l'année civile au cours de laquelle le personnel a 49 ans révolus et de 115 % dès le début de l'année civile au cours de laquelle le personnel a 50 ans révolus.
Art. 58 al. 2
2 Le service de garde est compté intégralement dans le temps de travail. Les heures de garde accomplies la nuit sont en outre compensées conformément à l'article 47a.
[...]
Art. 4
La présente ordonnance entre en vigueur le 1er janvier 2010".
6.2. Aux termes de l'art. 4 al. 1 CPJA-FR, sont des décisions les mesures de caractère obligatoire prises dans un cas d'espèce en application du droit public et qui ont pour objet: a) de créer, de modifier ou d'annuler des droits ou des obligations; b) de constater l'existence, l'inexistence ou le contenu de droits ou d'obligations; c) de rejeter ou de déclarer irrecevables des demandes tendant à créer, modifier, annuler ou constater des droits ou des obligations.
6.3.
6.3.1. En l'espèce, la juridiction cantonale a considéré:
"Au travers de son préambule, le Conseil d'Etat expose la genèse de l'ordonnance et en définit les modalités. Par les termes "sans effet rétroactif", le Conseil d'Etat a voulu s'adresser au personnel, déjà employé, ayant accompli des heures de garde ou de nuit avant le 1er janvier 2010. Il lui a directement signifié que les compensations désormais dues ne seraient pas concédées rétroactivement pour le temps de travail effectué dans le passé. Par ce biais, le Conseil d'Etat a ainsi confirmé ce qui avait déjà été annoncé durant la phase d'élaboration du projet d'ordonnance et au cours des négociations. (...) Ainsi, l'ordonnance avait, pour ce qui est de la question de la non-rétroactivité des prestations, vocation à s'appliquer directement à tous les collaborateurs et collaboratrices concerné-es en fonction d'une situation de fait suffisamment concrète, sans qu'il ne soit besoin de la mettre en oeuvre au moyen d'un autre acte de l'autorité.
Elle régissait ainsi:
- une situation déterminée (la non-rétroactivité de la compensation du travail de garde et de nuit pour des prestations effectuées avant le 1er janvier 2010),
- relative à un cercle relativement important de personnes (le personnel de l'Etat appartenant à une structure de l'Etat soumise à la LTr, comme le HFR et le RFSM, ayant effectué des prestations de nuit ou de garde dans les 5 ans précédant son entrée en vigueur).
Vu sa teneur, force est d'admettre que le préambule de l'ordonnance, spécialement sa dernière phrase, règle un point particulier qui revêt la nature juridique d'une décision générale. En revanche, il est incontestable que les articles introduits, édictés pour l'avenir, et non pas seulement pour réglementer les rapports avec le personnel déjà en activité au moment de l'adoption de l'ordonnance, respectivement de son entrée en vigueur, nécessiteront en revanche une mise en oeuvre concrète. Ces dispositions régissent en ce sens une situation générale et abstraite, et constituent ainsi un acte normatif.
Ainsi, l'on se trouve en présence du cas exceptionnel dans lequel la décision générale est intégrée à l'acte législatif." (jugement attaqué, consid. 3.2).
La juridiction cantonale s'est référée à la jurisprudence du Tribunal fédéral selon laquelle une décision générale s'adresse à un cercle relativement indéterminé de personnes et, d'autre part, règle un cas concret et doit être traitée comme une décision ordinaire lorsqu'elle peut être appliquée et exécutée sans autre mesure concrète d'une autorité (arrêts 8C_130/2014 déjà cité au consid. 4.1 supra et 2C_330/2013 du 10 septembre 2013, consid. 3.4.5). Au regard de ces principes jurisprudentiels, il n'est pas insoutenable de voir dans le préambule en cause une décision générale. On relèvera en particulier que ce texte énonce clairement que les dispositions de l'ordonnance s'appliqueront au personnel des établissements personnalisés de l'Etat ainsi que, par souci d'égalité de traitement, à tout le personnel de l'Etat. Le préambule précité mentionne également que des décisions ont été prises par le gouvernement cantonal "notamment sur l'entrée en vigueur progressive dès 2010, sans effet rétroactif".
Par ailleurs, les premiers juges ont pris en compte la jurisprudence selon laquelle un acte normatif cantonal peut exceptionnellement contenir des actes particuliers comme une décision générale (arrêt 2C_330/2013 précité, consid. 3.4.5), l'ensemble devant alors, en vertu du principe de l'apparence (sur cette notion, voir cette dernière référence et l'<ref-ruling> consid. 2.3 p 389), être soumis au régime juridique des actes normatifs cantonaux et aux voies de recours correspondantes.
Ces considérations, soigneusement étayées, sont en concordance avec la situation concrète. Elles reposent en outre sur des motifs objectifs. Ainsi, elles ne peuvent pas être qualifiées d'arbitraires.
6.3.2. Selon le recourant, en l'absence de mesures d'application ou d'exécution d'une autorité, le préambule ne remplirait pas les conditions d'une décision dès lors qu'un administré ne pourrait nullement se rendre compte de la portée de celui-ci, ni quels seraient ses droits et obligations partiellement touchés.
Le recourant ne saurait être suivi. En effet, il découle non seulement des motifs qui viennent d'être exposés, mais aussi du contenu de l'ordonnance elle-même et de son préambule, que les droits reconnus au personnel concerné ainsi que leur application temporelle - pour la période antérieure au 1 er janvier 2010 et pour la période postérieure à cette date - sont dûment énoncés et détaillés. Il ne suffit pas de prétendre que la lettre et la densité du préambule querellé ne permettent pas de lui reconnaître un caractère concret et directement applicable, pour que l'application qu'en a faite la juridiction cantonale puisse être qualifiée d'arbitraire. Le fait que le RFSM, puis le Conseil d'Etat ont rendu, dans cette cause, des décisions sur les prétentions du recourant n'est pas de nature à modifier cette appréciation. Car, toute autorité peut être appelée à se prononcer sur la prétention d'un administré, alors même qu'elle a rendu antérieurement une décision en la matière.
6.3.3. Par ailleurs, A._ estime le résultat de l'arrêt attaqué choquant du fait que ses prétentions antérieures au 1 er janvier 2010 reposent uniquement sur les dispositions impératives de la LTr en vigueur et applicables à cette période et non pas sur une application rétroactive de l'ordonnance. Dans le cadre de la présente procédure, il n'est pas possible d'évaluer les mérites de cette motivation. En effet, il s'agit ici de griefs qui auraient pu s'adresser éventuellement à l'ordonnance du Conseil d'Etat, comme acte normatif, mais ils ne sauraient conduire à qualifier d'insoutenables les considérations du jugement attaqué sur la voie qu'aurait dû emprunter le recourant pour faire valoir ses arguments.
6.4. Il découle de ce qui précède que c'est sans arbitraire que les juges précédents ont retenu que le recourant avait agi tardivement pour contester la non-rétroactivité de l'ordonnance en question, s'adressant au surplus à une autorité incompétente. Partant, le grief de déni de justice n'est pas fondé non plus.
7. Mal fondé, le recours doit être rejeté dans la mesure où il est recevable.
Succombant, le recourant doit supporter les frais de la procédure (<ref-law>). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 1500 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal de l'Etat de Fribourg, I re Cour administrative, et au Conseil d'Etat du canton de Fribourg.
Lucerne, le 15 mai 2020
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Juge présidant : Heine
La Greffière : Fretz Perrin