Faits:
A.
Sur la base des déclarations de plusieurs adolescents, il a été reproché les faits suivants à X._. Lors de ses cours de l'année scolaire 1997/1998, X._ était partiellement dissimulé par son pupitre, sa mallette ouverte devant lui. Régulièrement, après avoir donné du travail aux élèves, l'enseignant s'agitait et sautillait sur sa chaise en faisant trembler le plancher de la salle. Il gardait alors une ou les deux mains sous son pupitre. Après 5 à 10 minutes, il sortait un mouchoir en papier de sa mallette, le dépliait et remettait les mains sous son bureau. Par la suite, il se levait pour jeter le mouchoir dans la corbeille. Il se lavait les mains au lavabo au fond de la pièce ou sortait aux toilettes. Hormis l'utilisation d'un mouchoir en papier, X._ a admis les faits rapportés par les élèves. En revanche, il a contesté toute connotation sexuelle à son comportement, qui, selon ses explications, résulte en particulier de ses problèmes de santé, à savoir de la nécessité de devoir masser de façon occasionnelle une région douloureuse de son abdomen et de son tic qui consiste à croiser les jambes ou les pieds ce qui provoquerait un certain tremblement du sol et du pupitre.
Par jugement du 18 septembre 2001, le juge suppléant des districts de Martigny et St-Maurice a condamné X._, pour actes d'ordre sexuel avec des enfants (<ref-law>), à 12 mois d'emprisonnement et lui a interdit d'exercer la fonction d'enseignant durant 4 ans. Ces peines ont été assorties du sursis avec un délai d'épreuve de 3 ans.
Par jugement du 15 avril 2003, la Cour pénale II du Tribunal cantonal valaisan a acquitté X._ du chef d'accusation d'actes d'ordre sexuel avec des enfants. Elle a admis que ce dernier se masturbait durant les heures de classe. Elle a toutefois estimé qu'il devait être acquitté, le dol éventuel n'étant pas suffisant pour l'application de l'<ref-law> et le dol direct étant exclu au regard des précautions prises par l'enseignant. La cour cantonale a toutefois admis qu'en se masturbant en classe, le recourant avait adopté un comportement contraire à ses obligations et porté atteinte à la personnalité de ses élèves et que ces fautes étaient en rapport de causalité avec l'ouverture de la procédure pénale. Dans ces circonstances, elle a estimé que l'Etat n'avait pas à assumer les frais d'instruction, seuls les frais de jugement de première instance devant être mis à la charge de celui-ci. Ce faisant, elle a réparti les frais de première instance à raison de 2'495 fr. 65 à la charge du recourant et de 1'369 fr. à la charge de l'Etat, qui supportait, en sus, les frais d'appel.
Par arrêt du 7 août 2003 (6P.68/2003), le Tribunal fédéral a rejeté dans la mesure de sa recevabilité le recours de droit public formé par X._.
B.
Le 2 août 2013, invoquant les nouvelles déclarations d'un ancien élève, X._ a requis la révision du jugement du 15 avril 2003 en ce sens qu'il est reconnu qu'il ne s'est livré à aucun acte de masturbation, que les frais de procédure sont entièrement mis à la charge de l'Etat et qu'une indemnité pour tort moral de 20'000 fr. lui est allouée.
Par ordonnance du 26 septembre 2013, la Cour pénale II du Tribunal cantonal du canton du Valais a déclaré irrecevable la demande de révision.
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre cette ordonnance, concluant, avec suite de dépens, à son annulation et au renvoi de la cause à la cour cantonale pour qu'elle entre en matière sur la révision. Il a transmis ultérieurement la copie d'un article de presse.

Considérant en droit:
1.
Le mémoire contient sur une dizaine de pages un exposé personnel des faits. Ce faisant, le recourant ne formule aucune critique recevable.
La pièce nouvelle (article de presse) produite par le recourant, qui plus est après l'échéance du délai de recours, est irrecevable (<ref-law>).
2.
Le recourant se plaint d'une violation de l'<ref-law> et de l'art. 6 par. 2 CEDH.
2.1. La demande de révision et la décision attaquée sont postérieures à l'entrée en vigueur, le 1 er janvier 2011, du code de procédure pénale suisse. Il s'ensuit que les règles de compétence et de procédure des <ref-law> s'appliquent. Les motifs de révision pertinents sont en revanche ceux prévus par le droit applicable au moment où la décision dont la révision est demandée a été rendue, soit, en l'espèce, le 15 avril 2003. Cette réserve est toutefois sans portée en l'espèce s'agissant d'une révision en faveur, le motif de révision prévu à l'<ref-law> correspondant à celui de l'art. 397 aCP, respectivement de l'<ref-law>, qui n'a d'ailleurs formellement pas été abrogé (cf. arrêt 6B_393/2012 du 12 novembre 2012 consid. 1.1.1). Pour le surplus, le recourant n'invoque aucune disposition cantonale qui aurait été applicable en 2003 et qui lui serait plus favorable que le droit fédéral.
2.2. Dès lors que le jugement de 2003 a acquitté le recourant, il ne peut se prévaloir du motif de révision figurant à l'<ref-law>. Quant aux frais mis à sa charge par ledit jugement, la voie de la révision, que ce soit sous l'angle de l'<ref-law> ou de l'<ref-law>, respectivement de l'art. 397 aCP, n'est précisément pas ouverte pour cette question (cf. Message du 21 décembre 2005 relatif à l'unification du droit de la procédure, FF 2006 1057, p. 1303 ad art. 417 du projet; NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2 e éd. 2013, n° 8 ad <ref-law>; MARIANNE HEER, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n° 30 ad <ref-law>; TRECHSEL/LIEBER, Schweizerisches Strafgesetzbuch, Praxiskommentar, 2 e éd. 2013, n° 4 ad <ref-law> p. 1585). Par conséquent, contrairement à ce que suppose le recourant, la cour cantonale n'a pas violé le droit fédéral en refusant d'entrer en matière.
C'est aussi en vain que le recourant se prévaut de l'art. 6 CEDH. La condamnation d'un prévenu acquitté à supporter tout ou partie des frais doit respecter la présomption d'innocence, consacrée par les art. 32 al. 1 Cst. et 6 par. 2 CEDH (cf. <ref-ruling> consid. 1b p. 334; <ref-ruling> consid. 2c p. 168 ss). Il ne ressort pas de l'arrêt du Tribunal fédéral 6P.68/2003 du 7 août 2003 que le recourant aurait à l'époque contesté la réalisation des conditions permettant, sur la base de faits retenus, de mettre une partie des frais à sa charge nonobstant son acquittement. Il est forclos à revenir sur cet aspect. Il ne formule pas non plus de grief recevable selon l'<ref-law> pour soutenir que les art. 32 al. 1 Cst. et 6 par. 2 CEDH imposeraient d'ouvrir une voie de révision sur la question des frais.
3.
Le recours doit être rejeté dans la mesure où il est recevable. Le recourant, qui succombe, supporte les frais (<ref-law>).

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 à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et à la Cour pénale II du Tribunal cantonal du canton du Valais.
Lausanne, le 10 mars 2014
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet