Faits: A. P._ a été engagé en qualité de Xx._ par l'Aéroport international de Genève (ci-après: l'AIG) à partir du 1 er février 1996. Il a été nommé Xy._ en décembre 1998. Par décision du 21 décembre 2009, l'AIG a licencié P._ avec effet au 30 juin 2010, tout en le libérant de l'obligation de travailler dès le 1 er janvier 2010. L'intéressé a contesté son licenciement devant la commission de recours de l'AIG, laquelle l'a confirmé par décision du 15 septembre 2010. B. Par jugement du 5 avril 2011, la Chambre administrative de la Cour de justice de la République et canton de Genève a admis le recours de P._. Elle a constaté que le licenciement était contraire au droit, proposé la réintégration de l'employé et ordonné à l'AIG, en cas de refus de procéder à cette réintégration, de transmettre sa décision à la Chambre administrative pour fixation d'une indemnité. Le 3 juillet 2012, P._ a saisi la Chambre administrative d'une demande en fixation de l'indemnité. Par lettre du 9 juillet 2012, l'AIG a informé la Chambre administrative qu'il n'entendait pas réintégrer P._ dans son ancien poste et a requis un délai au 27 juillet suivant pour se déterminer sur l'indemnité maximale réclamée par ce dernier. L'AIG a soumis sa prise de position le 17 juillet 2012. Le 12 mars 2013, la Chambre administrative de la Cour de justice a rendu un jugement par lequel elle a condamné l'AIG à verser à P._ une indemnité correspondant à douze fois son dernier traitement brut avec intérêts à 5 % à compter du 9 juillet 2012. C. P._ interjette un recours en matière de droit public contre ce jugement, dont il demande l'annulation. Sous suite de frais et dépens, il conclut, principalement, à ce que l'AIG soit condamné à lui verser une indemnité correspondant à dix-huit mois de salaire et que le tribunal constate qu'il s'agit d'une indemnité à caractère punitif. Subsidiairement, il conclut au renvoi de la cause à la Chambre administrative pour qu'elle statue dans le sens des considérants. L'AIG conclut au rejet du recours. Il requiert par ailleurs l'octroi de l'effet suspensif. D. Par ordonnance du 3 octobre 2013, le juge instructeur a rejeté la demande d'effet suspensif.