Faits :
A.
A.a. A._ travaillait en qualité d'agent de piste auprès de la société B._ et était, à ce titre, assuré contre les accidents auprès de la Caisse nationale suisse d'assurance en cas d'accidents (CNA). Le 4 octobre 1995, il a subi une distorsion au genou droit en jouant au football, laquelle a nécessité une arthroscopie avec méniscectomie partielle du ménisque interne droit. Le cas a été pris en charge par la CNA. Le 7 mai 2008, l'assuré a été victime d'un accident de moto ayant entraîné des dermabrasions et des contusions au niveau du côté droit. Il a pu rependre son travail à 100 % dès le 12 mai 2008. La CNA est également intervenue dans les suites de ce sinistre. Le 15 juin 2008, l'assuré a été admis en urgence au service de neurochirurgie de l'hôpital C._ où il a subi une laminectomie C4 pour tétraparésie sub C4 sur canal étroit décompensé. L'incapacité de travail de l'assuré a été totale depuis lors.
A.b. Souffrant de douleurs et de lâchages au niveau du genou droit, A._ a été soumis à une IRM le 10 mars 2009, laquelle a fait état d'une chondrocalcinose sévère et d'une gonarthrose; le 8 septembre 2009, il a subi une arthroscopie avec toilette articulaire. En raison d'une évolution difficile avec inflammation récidivante, une prothèse totale a été implantée au niveau de son genou droit le 6 mai 2010. La CNA a reconnu sa responsabilité pour les troubles au genou droit annoncés en mars 2009, lesquels étaient constitutifs d'une rechute de l'accident du 4 octobre 1995.
Par décision du 19 juillet 2011, confirmée sur opposition le 24 février 2012, la CNA a accepté de prendre en charge les frais de traitement en lien avec l'atteinte au genou droit dès le 10 mars 2009 mais a refusé de verser des indemnités journalières, l'assuré étant déjà au bénéfice d'une rente entière de l'assurance-invalidité depuis le 1 er juin 2009 pour cause de maladie (troubles neurologiques; cf. décision du 18 novembre 2010). Saisie d'un recours de l'assuré, la Chambre des assurances sociales de la Cour de justice de la République et canton de Genève a annulé les décisions des 19 juillet 2011 et 24 février 2012 et a renvoyé la cause à la CNA pour qu'elle mette en oeuvre une expertise neurologique et orthopédique établissant l'évolution dans le temps de l'incapacité de travail liée aux atteintes neurologique et du genou puis rende une nouvelle décision (cf. arrêt de la Chambre des assurances sociales du 29 août 2013).
La CNA a alors mandaté des médecins du Service de neurologie de l'hôpital D._, lesquels ont rendu leur rapport le 7 août 2015. En substance, les experts ont constaté qu'au moment de la rechute annoncée le 10 mars 2009, la capacité de travail de l'assuré dans sa profession habituelle était entière, compte tenu de la seule problématique au genou droit. Entre le 10 mars 2009 et le 6 mai 2010, l'évolution sur le plan neurologique avait été favorable tandis que la pathologie arthrosique de genou était devenue prépondérante par rapport aux séquelles de myélopathie cervicale. La reprise des activités n'avait pas été possible jusqu'à l'arthroplastie du genou droit le 6 mai 2010. Postérieurement à ladite intervention, les experts ont retenu qu'en faisant abstraction des autres pathologies, les douleurs persistantes au niveau du genou associées à un épanchement et à une pseudolaxité empêchaient l'exercice de l'activité d'agent de sûreté à 100 %. En revanche, l'exercice d'une activité adaptée était possible à 100 %, à condition d'éviter l'usage intensif des escaliers, le port de charges de plus de 20 kilos, la station debout prolongée et la marche rapide ou la course.
A.c. Par décision du 24 février 2017, confirmée sur opposition le 25 août 2017, la CNA a alloué à l'assuré une rente d'invalidité fondée sur une incapacité de gain de 40 % dès le 1 er juin 2010 et calculée sur la base d'un gain assuré de 68'686 fr. Elle lui a en outre accordé une indemnité pour atteinte à l'intégrité de 25 %.
B.
A._ a recouru contre la décision sur opposition devant la juridiction cantonale, en concluant à l'octroi d'une rente d'invalidité calculée sur la base d'un gain assuré de 96'558 fr.
La cour cantonale a rejeté ce recours par jugement du 4 octobre 2018.
C.
A._ forme un recours en matière de droit public contre ce jugement dont il requiert l'annulation, en concluant à l'octroi d'une rente d'invalidité mensuelle de 2574 fr. dès le 1 er juin 2010, fondée sur un gain assuré de 96'558 fr.
La CNA renvoie aux considérants du jugement attaqué, tandis que la cour cantonale a renoncé à se déterminer.

Considérant en droit :
1.
Le recours est dirigé contre un arrêt final (<ref-law>) rendu en matière de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF). Il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi.
2.
Le recours en matière de droit public peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>), n'étant limité ni par les arguments de la partie recourante, ni par la motivation de l'autorité précédente. Le Tribunal fédéral n'examine en principe que les griefs invoqués, compte tenu de l'exigence de motivation prévue à l'<ref-law>, et ne peut aller au-delà des conclusions des parties (<ref-law>). La présente procédure porte sur l'octroi ou le refus de prestations en espèces de l'assurance-accidents, de sorte que le Tribunal fédéral n'est pas lié par l'état de fait constaté par la juridiction précédente (art. 97 al. 2 et art. 105 al. 3 LTF).
3.
3.1. Il n'est pas contesté que le recourant a droit à une rente d'invalidité d'un taux de 40 % depuis le 1 er juin 2010 en raison d'une rechute de l'accident survenu le 4 octobre 1995. Est seul litigieux le montant du gain assuré servant à la fixation de la rente allouée au recourant.
3.2. Le 1 er janvier 2017 est entrée en vigueur la modification du 25 septembre 2015 de la LAA. Dans la mesure où tant l'accident que la rechute sont survenus avant cette date, le droit du recourant aux prestations d'assurance est soumis à l'ancien droit (cf. dispositions transitoires relatives à la modification du 25 septembre 2015). Les dispositions visées seront citées ci-après dans leur teneur en vigueur jusqu'au 31 décembre 2016.
4.
4.1. Selon l'<ref-law>, les indemnités journalières et les rentes sont calculées d'après le gain assuré (al. 1); est déterminant pour le calcul des rentes le salaire que l'assuré a gagné durant l'année qui a précédé l'accident (al. 2, deuxième phrase; cf. également l'art. 22 al. 4, première phrase OLAA). Le Conseil fédéral édicte des prescriptions sur le gain assuré pris en considération dans des cas spéciaux (al. 3). Faisant usage de cette délégation de compétence, le Conseil fédéral a édicté l'<ref-law> sous le titre marginal "Salaire déterminant pour les rentes dans des cas spéciaux". Lorsque le droit à la rente naît plus de cinq ans après l'accident ou l'apparition de la maladie professionnelle, le salaire déterminant est celui que l'assuré aurait reçu, pendant l'année qui précède l'ouverture du droit à la rente, s'il n'avait pas été victime de l'accident ou de la maladie professionnelle, à condition toutefois que ce salaire soit plus élevé que celui qu'il touchait juste avant la survenance de l'accident ou l'apparition de la maladie professionnelle (<ref-law>).
4.2. En l'occurrence, la juridiction cantonale a confirmé le montant du gain assuré de 68'686 fr. pris en compte par la CNA pour calculer le montant de la rente d'invalidité du recourant. Le droit à la rente de l'assuré étant né le 1 er juin 2010, soit plus de cinq ans après l'accident du 4 octobre 1995, la CNA a fait application de l'<ref-law> et retenu que le salaire déterminant était celui que l'assuré aurait réalisé du 1 er juin 2009 au 31 mai 2010 s'il n'avait pas été victime de l'accident. Pour calculer ce revenu, elle a pris en compte les données salariales de l'assuré pour la période courant du 4 octobre 1994 au 3 octobre 1995 (année précédant l'accident initial). Selon l'extrait du livre de paie transmis le 10 novembre 2015 par l'Office du personnel de l'Etat de Genève, la rémunération de l'assuré s'élevait alors à 58'203 fr. 90. Ce montant a ensuite été adapté à la période de calcul déterminante, soit à celle allant du 1er juin 2009 au 31 mai 2010. L'indice nominal hommes/femmes sur la base 1993 = 100 était de 101 points en 1995 et de 111.6 points en 2005 pour la branche référencée sous la Section I ("transports et communication"), de sorte que le gain annuel assuré en 2005 devait être fixé à 64'312 fr. 43 (58'203 fr. 90 x 111.6 / 101). L'indice nominal hommes/femmes sur la base 2005 = 100 étant de 106.8 points en 2010, le salaire déterminant était de 68'686 fr. (64'312 fr. 43 x 106.8 / 100).
4.3. Le recourant conteste la jurisprudence du Tribunal fédéral selon laquelle, dans le cas où la rente naît plus de cinq ans après l'accident (<ref-law>), l'adaptation du gain assuré ne doit pas se faire concrètement compte tenu de l'avancement professionnel présumé ou effectif et de l'augmentation correspondante du revenu, mais sur la base de l'évolution des salaires nominaux dans le domaine d'activité antérieur (cf. consid. 5.2 infra).
Le recourant demande que le salaire déterminant pris en compte pour le calcul de sa rente soit celui effectivement reçu pendant l'année précédant l'ouverture du droit à la rente et non pas un salaire hypothétique, ce qui se justifierait également sous l'angle du principe d'équivalence. Il fait en outre valoir que la solution retenue par les premiers juges ne serait pas non plus conforme aux principes constitutionnels de l'égalité de traitement (art. 8 Cst.) et de l'interdiction de l'arbitraire (art. 9 Cst.), dès lors qu'en adaptant le salaire annuel assuré déterminant uniquement à l'évolution nominale des salaires, on défavoriserait sans motif objectif les assurés victimes d'un accident en début de carrière, pour lesquels les effets sur la capacité de gain ne se produisent que plusieurs dizaines d'années plus tard, par rapport aux assurés victimes d'un accident en fin de carrière, pour lesquels les conséquences sur la capacité de gain sont immédiates. Le recourant soutient enfin que l'indemnité journalière et la rente reposant pour l'essentiel sur les mêmes bases de calcul, il conviendrait d'interpréter l'<ref-law> de manière concordante avec l'<ref-law> et de tenir compte de son salaire déterminant durant l'année précédant l'ouverture du droit à la rente, soit un montant de 96'558 fr.
5.
5.1. Selon la jurisprudence, l'<ref-law> n'est pas seulement applicable lorsque la naissance du droit à la rente est différée en raison de la prolongation du processus de guérison après un accident, mais également lorsqu'on procède pour la première fois à la fixation de la rente après plusieurs accidents invalidants et que le droit à la rente naît plus de cinq ans après le premier accident (<ref-ruling> consid. 3c p. 50 s.). De même, le gain assuré doit aussi être déterminé conformément à l'<ref-law> lorsqu'on procède pour la première fois à la fixation de la rente après une rechute (ou des séquelles tardives) survenue (s) plus de cinq ans après l'accident (<ref-ruling> consid. 6.1.2 p. 44; arrêt U 427/99 du 10 décembre 2001 consid. 3a, non publié in <ref-ruling>; SVR 2012 UV n° 3 p. 9 consid. 3.1.2, arrêt 8C_237/2011 du 19 août 2011; arrêt U 286/01 du 8 mars 2002 consid. 2b).
Il résulte de ce qui précède que le salaire déterminant pour le droit à la rente du recourant est celui qu'il aurait reçu pendant l'année qui précède l'ouverture du droit à la rente (le 1er juin 2010), s'il n'avait pas été victime de l'accident et de la rechute, à condition que ce salaire soit plus élevé que celui qu'il touchait avant la survenance de l'accident (le 4 octobre 1995). Il convient dès lors d'examiner le montant du gain assuré contesté par le recourant.
5.2. Selon la jurisprudence, l'<ref-law> a uniquement pour but de ne pas désavantager les assurés dont le droit à la rente naît plusieurs années après l'événement accidentel par rapport à ceux qui se voient octroyer la rente plus tôt, quand une forte augmentation des salaires s'est produite dans l'intervalle (<ref-ruling> consid. 3b p. 173; arrêt U 308/04 du 16 janvier 2006 consid. 3.1). En revanche, il n'y a pas lieu de placer l'assuré dans la situation qui serait la sienne si l'accident était survenu immédiatement avant l'ouverture du droit à la rente. La prise en compte, au moment de la fixation du droit à la rente, de l'évolution des salaires auprès du dernier employeur irait en substance au-delà du but réglementaire. Celui-ci consiste dans l'adaptation du gain assuré à l'évolution générale des salaires, c'est-à-dire à l'évolution normale du salaire dans le domaine d'activité habituelle. Aussi faut-il écarter tout autre changement dans les conditions salariales survenu depuis l'accident ou qui aurait pu se produire si l'accident n'avait pas eu lieu, comme une promotion professionnelle ou un changement d'employeur (<ref-ruling> consid. 3b p. 173, 118 V 298 consid. 3b p. 303) et considérer avec retenue toute évolution du salaire dans l'entreprise qui pourrait être influencée par l'assuré ou dépendre de lui. Or la prise en compte de l'évolution des salaires nominaux dans le domaine d'activité antérieur tient compte précisément de l'évolution intervenue, tout en écartant les facteurs étrangers au but visé à l'<ref-law>. C'est pourquoi elle est le mieux à même de mettre en oeuvre cette disposition réglementaire, en conformité avec le principe de l'égalité de traitement (arrêt 8C_760/2014 du 15 octobre 2015, consid. 5.3.2 et les références).
5.3. En outre, contrairement à ce que prétend le recourant, il convient de rappeler que les bases de calcul dans le temps du gain assuré sont différentes pour l'indemnité journalière et pour la rente (<ref-law>). En effet, l'indemnité journalière est calculée sur la base du salaire que l'assuré a reçu en dernier lieu avant l'accident, y compris les éléments de salaire non encore perçus et auxquels il a droit (<ref-law>). En principe, on ne tient pas compte de ce que l'assuré aurait gagné après l'accident. L'indemnité journalière ne se fonde donc pas sur un salaire hypothétique mais sur le revenu dont l'assuré victime d'un accident est effectivement privé en raison de la réalisation du risque assuré (méthode de calcul concrète; <ref-ruling> consid. 5b p. 173; SVR 2006 UV n° 6 p. 20, U 357/04 du 22 septembre 2005 consid. 1.5.4; JEAN-MAURICE FRÉSARD/MARGIT MOSER-SZELESS, L'assurance-accidents obligatoire, in: Schweizerisches Bundesverwaltungsrecht [SBVR], 3 e éd., 2016, n° 179 p. 956). Les rentes sont calculées quant à elles sur la base du salaire que l'assuré a reçu d'un ou de plusieurs employeurs durant l'année qui a précédé l'accident, y compris les éléments de salaire non encore perçus auxquels il a droit (art. 22 al. 4, première phrase, OLAA). Sont déterminants pour fixer le gain assuré le rapport de travail et les circonstances salariales qui existaient au moment de l'événement accidentel assuré, sans tenir compte des modifications du salaire qui seraient éventuellement intervenues sans l'accident (méthode de calcul abstraite; SVR 2006 UV n° 6 p. 20 consid. 1.5.4 déjà cité; JEAN-MAURICE FRÉSARD/MARGIT MOSER-SZELESS, op. cit., n° 182 p. 956). Le Conseil fédéral a cependant apporté certains correctifs à la règle du dernier salaire obtenu avant l'accident, tant pour l'indemnité journalière que pour les rentes. C'est ainsi que selon l'<ref-law>, le salaire déterminant en cas de rechute n'est pas le dernier salaire obtenu avant l'accident mais le salaire que l'assuré recevait juste avant la rechute. Le gain assuré déterminant pour la rente peut ainsi être nettement inférieur à celui déterminant pour l'indemnité journalière dans le cas où, comme en l'espèce, il s'agit de statuer pour la première fois sur la rente en cas de rechute survenue plus de cinq ans après l'accident (DOROTHEA RIEDI HUNOLD, in: Hürzeler/Kieser [éd.], UVG, Bundesgesetz über die Unfallversicherung, 2018, n° 33 ad <ref-law>).
5.4. Par ailleurs, le recourant ne saurait pas non plus se fonder sur le principe d'équivalence (cf. à cet égard <ref-ruling> consid. 4a p. 173) pour voir son gain assuré déterminant ajusté au-dessus de l'évolution du salaire nominal. En effet, il a déjà été jugé que le principe d'équivalence n'est pas enfreint si la rente est calculée sur la base du gain assuré au moment de l'accident et adapté à l'évolution nominale des salaires jusqu'à l'ouverture du droit à la rente (arrêt U 286/01 du 8 mars 2002 consid. 3b/cc). De même, le principe d'équivalence n'est pas non plus remis en cause lorsque l'assuré a payé des primes sur un revenu plus élevé après l'accident dès lors qu'en cas de nouvel accident, c'est le salaire reçu durant l'année précédant ce dernier qui serait alors déterminant (<ref-law>; <ref-ruling> consid. 3a p. 49; arrêt U 286/01 précité consid. 3b/cc).
5.5. Vu ce qui précède, il n'y a pas lieu de revenir sur la jurisprudence selon laquelle l'adaptation du gain assuré déterminant pour la fixation de la rente née plus de cinq ans après l'accident (<ref-law>) ne doit pas se faire concrètement selon l'évolution des salaires auprès du dernier employeur mais en fonction de l'évolution des salaires nominaux dans le domaine d'activité antérieur.
Cela étant, le montant annuel du gain assuré fixé par l'intimée et confirmé par la cour cantonale ne prête pas le flanc à la critique, de sorte que le recours doit être rejeté.
6.
Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties, à la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, et à l'Office fédéral de la santé publique.
Lucerne, le 23 mars 2020
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président : Maillard
La Greffière : Fretz Perrin