Faits:
A.
Les parcelles nos 80 et 89 de la commune d'Hérémence se situent au lieu-dit "Maqueyblan", à l'entrée du Val des Dix. Propriétés de X._ depuis 1998, elles sont classées en zone agricole. Un chalet est construit de longue date sur la parcelle n° 89.
En septembre 2005, la police des constructions de la Commission cantonale des constructions (ci-après: la CCC) a constaté que divers travaux de rénovation du chalet (toiture), de transformations (pose de six velux et création d'ouvertures en façades) et d'aménagements extérieurs (terrasse, grill, piste de pétanque, route d'accès, etc.) étaient en cours sur ces parcelles. X._ a expliqué, le 14 novembre 2005, que ces travaux d'entretien avaient en réalité débuté au printemps 1991, à la suite des dégâts causés par le tempête "Viviane", avec l'approbation que la commune d'Hérémence avait donnée à l'ancien propriétaire. Il indiquait qu'il les avait poursuivis dès qu'il avait acquis le chalet en 1998, sans modifier le gabarit du bâtiment ni créer de nouveaux aménagements extérieurs.
La CCC a exigé le dépôt d'une demande d'autorisation de construire, obligation à laquelle X._ s'est conformé après deux rappels, le 26 octobre 2006, produisant plusieurs plans à main levée qui portaient pour l'essentiel sur de futurs aménagements. Le 18 octobre 2007, la CCC a ordonné l'arrêt des travaux en cours. Après avoir tenté en vain d'obtenir de X._ des informations complémentaires, elle a ordonné la remise en état des lieux le 14 décembre 2009; cette décision concernait l'ensemble des aménagements extérieurs. Les travaux de rénovation et de transformation du chalet ont fait l'objet d'une autre décision, rendue quatre jours plus tôt, aux termes de laquelle l'intéressé devait déposer une demande d'autorisation de construire, avec mise à l'enquête publique, dans un délai de soixante jours.
B.
X._ a attaqué l'ordre de remise en état des lieux devant le Conseil d'Etat, qui a déclaré, le 16 février 2011, son recours irrecevable pour cause de tardiveté. Entretemps, l'intéressé avait déposé une demande de reconsidération devant la CCC, en s'appuyant notamment sur des renseignements remis le 8 janvier 2010 par l'ancien propriétaire et sur des orthophotos de 1999, 2005 et 2008. La CCC a décidé de maintenir sa décision, le 4 février 2010. Une nouvelle demande de reconsidération n'a pas fait infléchir la position de cette autorité.
Le 4 août 2011, X._ a sollicité une nouvelle fois de la CCC la reconsidération de l'ordre de remise en état des lieux du 14 décembre 2009. A l'appui de cette demande, il a déposé en particulier plusieurs pièces témoignant selon lui de la préexistence des aménagements extérieurs, soit des orthophotos de 1982 et de 1994, ainsi que cinq attestations de mai 2010 émanant de diverses personnes impliquées dans la réalisation des travaux litigieux. Il a également produit une autorisation de construire du 12 octobre 1990 émanant de la commune d'Hérémence ainsi qu'une détermination de celle-ci du 20 avril 2010.
La CCC a refusé d'entrer en matière, le 6 octobre 2011. Le Conseil d'Etat a rejeté le recours de l'intéressé contre cette décision, le 6 juin 2012.
Par arrêt du 20 décembre 2012, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours de X._ contre la décision du Conseil d'Etat du 6 juin 2012, dans la mesure où il était recevable. Le Tribunal cantonal a considéré en substance que les conditions auxquelles la CCC est tenue de reconsidérer sa décision ne sont pas remplies.
C.
Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral d'annuler l'arrêt du Tribunal cantonal du 20 décembre 2012 et de renvoyer la cause à la cour cantonale afin qu'il soit entré en matière et instruit sur la demande en reconsidération. Il se plaint pour l'essentiel d'une constatation inexacte des faits et d'une appréciation arbitraire des preuves ainsi que d'une violation du droit d'être entendu et du droit à la preuve.
Le Tribunal cantonal et la CCC renoncent à se déterminer. Le Conseil d'Etat renvoie à la motivation de l'arrêt attaqué et conclut au rejet du recours. La commune d'Hérémence renvoie au dossier cantonal.

Considérant en droit:
1.
Dirigé contre une décision rendue dans le domaine du droit public de l'aménagement du territoire et des constructions, le recours est en principe recevable comme recours en matière de droit public conformément aux <ref-law>, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. Le recourant a pris part à la procédure de recours devant le Tribunal cantonal. Il est particulièrement touché par l'arrêt attaqué qui confirme le refus de la CCC de reconsidérer son ordre de remise en état des lieux du 14 décembre 2009. Il peut ainsi se prévaloir d'un intérêt personnel et digne de protection à son annulation ou à sa modification. Il a dès lors qualité pour agir au sens de l'<ref-law>.
2.
L'objet du litige porte sur une demande de reconsidération. Il s'agit en l'occurrence de déterminer si c'est à bon droit que les autorités cantonales ont refusé d'entrer en matière sur la requête du recourant qui demandait à la CCC de réexaminer la décision de remise en état des lieux du 14 décembre 2009.
Sous certaines conditions, les autorités administratives peuvent réexaminer leurs décisions. Elles sont toutefois tenues de le faire si une disposition légale ou une pratique administrative constante les y oblige. Tel est le cas de l'art. 33 al. 2 de la loi cantonale valaisanne du 6 octobre 1976 sur la procédure et la juridiction administratives (LPJA), qui prévoit qu'une autorité n'est tenue de reconsidérer sa décision que si les circonstances ont été modifiées dans une notable mesure depuis la première décision (let. a) ou si le requérant invoque des faits ou des moyens de preuve importants dont il ne s'est pas prévalu dans la procédure antérieure, soit qu'il n'était pas en mesure de le faire, soit qu'il n'existait aucun motif pour le faire (let. b).
La jurisprudence a en outre déduit des garanties générales de procédure de l'art. 29 al. 1 et 2 Cst. l'obligation pour l'autorité administrative de se saisir d'une demande de réexamen lorsque les circonstances de fait ont subi, depuis la première décision, une modification notable, ou si le requérant invoque des faits ou des moyens de preuve importants qu'il ne connaissait pas lors de la première décision, ou dont il ne pouvait pas se prévaloir ou n'avait pas de raison de se prévaloir à cette époque (arrêt 2A.506/2003 du 6 janvier 2004, SJ 2004 I p. 389, consid. 2; <ref-ruling> consid. 3a p. 6; <ref-ruling> consid. 2b p. 46 s.; <ref-ruling> consid. 3a p. 151 s.). Le réexamen de décisions administratives entrées en force ne doit pas être admis trop facilement. Il ne saurait en particulier servir à remettre sans cesse en cause des décisions exécutoires ou à détourner les délais prévus pour les voies de droit ordinaires (cf. <ref-ruling> consid. 2.1 p. 181).
3.
En l'espèce, à l'appui de sa demande de reconsidération, le recourant a déposé notamment des orthophotos de 1982 et de 1994, des attestations de mai 2010 émanant de diverses personnes impliquées dans la réalisation des travaux litigieux ainsi qu'une autorisation de construire du 12 octobre 1990 de la commune d'Hérémence et une détermination du 20 avril 2010 de cette dernière. Le Tribunal cantonal a considéré qu'aucune de ces pièces ne permettait d'entrer en matière sur la demande de reconsidération.
3.1. S'agissant des orthophotos, le Tribunal cantonal a relevé que celles-ci avaient été retrouvées au cadastre communal à la suite d'une demande de recherche que le recourant avait présentée en juin ou juillet 2011. C'est ainsi à juste titre que les juges cantonaux ont considéré que le caractère objectivement nouveau de ces pièces au sens de l'art. 33 LPJA ne pouvait être admis. En effet, le recourant savait depuis le mois d'octobre 2005 que la CCC s'intéressait aux aménagements extérieurs construits sur ses parcelles et elle lui avait transmis les 21 novembre 2007 et 9 octobre 2008 un formulaire qu'elle l'invitait à remplir afin de déterminer l'époque de réalisation de ces aménagements. Le recourant n'y a pas donné suite, alors qu'il lui appartenait de collaborer à l'établissement des faits, s'agissant d'éléments qui sont de nature à lui procurer un avantage et qu'il est censé connaître mieux que quiconque (<ref-ruling> consid. 2b p. 142; cf. également <ref-ruling> consid. 3.2 non publié et les références). Dans ces conditions, l'intéressé est malvenu de se plaindre d'une violation des règles essentielles de procédure et de son droit d'être entendu, alors qu'il avait tout le loisir de fournir les documents nécessaires en cours de procédure et qu'il avait été formellement invité à le faire. De même, le recourant ne montre pas en quoi les juges cantonaux auraient constaté les faits de manière arbitraire en relevant que, s'il avait fait montre de l'attention requise par les circonstances, il aurait été en mesure de produire les orthophotos en question avant que la CCC ne rende son ordre de remise en état des lieux.
A titre superfétatoire, le Tribunal cantonal a estimé que ces pièces n'étaient au demeurant pas importantes, au sens de l'art. 33 al. 2 let. b LPJA, puisque leur qualité ne permettait pas de démontrer l'existence des aménagements litigieux ni de remettre en cause le constat éloquent qui ressortait de la comparaison des orthophotos de 1999 et 2005 quant à l'évolution des travaux extérieurs. Cette motivation relative à l'appréciation anticipée des preuves échappe à l'arbitraire (à ce sujet, cf. <ref-ruling> consid. 3 p. 157 et les arrêts cités; sur la notion d'arbitraire, voir <ref-ruling> consid. 5.1 p. 17). Le Tribunal cantonal pouvait dès lors, sans violer le droit d'être entendu de l'intéressé, renoncer à ordonner une expertise destinée à analyser les nouvelles orthophotos et à prouver leur pertinence, comme celui-ci le demandait.
Mal fondés, les griefs du recourants relatifs à l'application et à l'interprétation arbitraire du droit cantonal, à la violation des règles essentielles de procédure et au déni de justice formel, à la violation du droit d'être entendu, à la constatation inexacte des faits et à l'abus du pouvoir d'appréciation, en tant que le Tribunal cantonal a considéré que les orthophotos de 1982 et de 1994 n'étaient pas des pièces nouvelles et importantes, doivent être rejetés.
3.2. Le Tribunal cantonal a ensuite retenu que l'écrit du 12 juillet 2011 signé par A._, entreprise de terrassement, avait été établi après la fin de la procédure ordinaire de police des constructions et visait des faits antérieurs à celle-ci. Le recourant avait déjà déposé des pièces de ce type émanant d'artisans chargés de travaux sur ses parcelles à l'appui d'une précédente demande de reconsidération, sur laquelle la CCC n'était pas entrée en matière. Dans la mesure où le recourant s'était abstenu de contester cette décision par un recours, il ne pouvait s'appuyer sur un moyen de preuve semblable aux précédents pour motiver le dépôt d'une nouvelle demande de reconsidération.
Le recourant affirme que l'appréciation des preuves effectuée par le Tribunal cantonal relève de l'arbitraire et de l'abus du pouvoir d'appréciation. A l'appui de sa motivation, il fait valoir que le caractère nouveau du moyen de preuve ne saurait être exclu du simple fait que d'autres attestations, émanant de témoins différents, avaient été produites antérieurement. Le Tribunal cantonal aurait dû au contraire constater que les attestations en question remettaient en cause l'appréciation faite par la commune d'Hérémence s'agissant de l'ordre de remise en l'état. Ce faisant, le recourant ne démontre pas en quoi l'appréciation précitée des juges cantonaux serait insoutenable, ce qui n'apparaît pas être le cas. En effet, il lui appartenait de produire toutes les attestations au cours de la procédure devant la CCC, ou au plus tard dans sa première demande de reconsidération. Une procédure close ne peut pas être indéfiniment reprise, au gré de nouveaux témoignages; tel ne saurait de toute façon être le cas lorsque rien n'empêchait l'intéressé de recueillir auparavant ces déclarations écrites. Mal fondé, ce grief doit également être rejeté.
3.3. Le Tribunal cantonal a enfin refusé de prendre en compte la demande d'autorisation de construire déposée par l'ancien propriétaire le 21 août 1990 et admise le 8 octobre suivant par la commune. Il a en effet jugé que ces pièces n'étaient pas nouvelles, le recourant les ayant déjà produites devant la CCC à l'appui de sa demande de reconsidération du 2 juin 2010. Les juges cantonaux ont également considéré que cette autorisation de construire ne concernait que la réparation du chalet et non d'éventuels travaux d'aménagements extérieurs, seuls litigieux, pour lesquels aucune autorisation en bonne et due forme n'a été versée au dossier, comme l'avait établi le Conseil d'Etat.
Selon le recourant, la cour cantonale a procédé à une constatation arbitraire des faits en considérant que les autorisations de construire faisaient défaut au dossier. Il allègue qu'il a produit l'autorisation de la commune d'Hérémence du 8 octobre 1990 et que, dans son courrier du 20 avril 2010, la commune avait indiqué que la réparation du chalet avait été entreprise de bonne foi par l'ancien propriétaire. L'autorisation de construire produite démontrait ainsi que les constructions litigieuses avaient été entreprises par l'ancien propriétaire avant 1998, conformément au droit en vigueur, de sorte qu'il convenait d'entrer en matière sur la demande de reconsidération. Le recourant perd de vue que l'autorisation de construire du 8 octobre 1990 sur laquelle il se fonde concerne la réparation du chalet et non les travaux d'aménagements extérieurs litigieux. Il apparaît dès lors que c'est sans tomber dans l'arbitraire que le Tribunal cantonal a constaté, à la suite du Conseil d'Etat, qu'aucune autorisation en bonne et due forme n'avait été versée au dossier concernant les abords du chalet.
4.
Il résulte de ce qui précède que le recours, entièrement mal fondé, doit être rejeté aux frais du recourant qui succombe (art. 65 et 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au recourant, à la Commune d'Hérémence, au Conseil d'Etat et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 29 août 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
La Greffière: Mabillard