Sachverhalt:
A.
Am 26. April 2012 hat der aus dem Kosovo stammende X._ (geb. 1952) in seinem Herkunftsland die kosovarische Staatsangehörige A._ (geb. 1972) geheiratet. Bereits vorgängig hatte A._ am 17. Oktober 2011 ein Gesuch um Einreise zur Ehevorbereitung gestellt, wobei die Brautleute zu diesem Zeitpunkt einzig telefonisch und auf elektronischem Weg miteinander kommuniziert hatten und eine erste persönliche Begegnung noch ausstand. Nach erfolgter Heirat reichte A._ am 24. Mai 2012 ein Gesuch um Familiennachzug ein.
B.
Mit Verfügung vom 30. März 2012 wies das Migrationsamt des Kantons Zürich das Gesuch um Einreise zur Ehevorbereitung ab, da von einem rechtsmissbräuchlichen Handeln auszugehen sei und folglich nach dem Eheschluss kein Anspruch auf eine Aufenthaltsbewilligung bestehe. Im anschliessenden Rekursverfahren verneinte die Sicherheitsdirektion des Kantons Zürich, welcher das Gesuch vom 24. Mai 2012 zuständigkeitshalber überwiesen wurde, mit Entscheid vom 30. Juli 2012 einen Anspruch auf Familiennachzug und wies den Rekurs ab. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 20. Dezember 2012 ab. Im Verlaufe des Beschwerdeverfahrens wurde X._ eingebürgert.
C.
Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 20. Dezember 2012 aufzuheben und das Migrationsamt des Kantons Zürich anzuweisen, A._ den Familiennachzug zu bewilligen. Ferner sei ihm die unentgeltliche Rechtspflege zu gewähren.
Die Sicherheitsdirektion des Kantons Zürich und das Bundesamt für Migration (BFM) beantragen die Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich verzichtete auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer ist Schweizer Bürger und seit dem 26. April 2012 mit A._ verheiratet. Er hat grundsätzlich einen gesetzlich (Art. 42 Abs. 1 AuG [SR 142.20]) wie verfassungs- (<ref-law>) bzw. konventionsmässig (Art. 8 Ziff. 1 EMRK) begründeten Anspruch darauf, seine Ehefrau in die Schweiz nachziehen zu können (Urteil 2C_1170/2012 vom 24. Mai 2013 E. 1.1). Ob die entsprechenden Voraussetzungen erfüllt sind, ist eine Frage der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179 f.; Urteil 2C_195/2012 vom 2. Januar 2013 E. 1.1, nicht publ. in: <ref-ruling>). Auf die form- und fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den kantonal letztinstanzlichen Endentscheid (<ref-law>) ist daher grundsätzlich einzutreten (vgl. Art. 82 i.V.m. Art. 83 lit. c Ziff. 2 [e contrario], Art. 86 Abs. 1 lit. d und Art. 89 BGG).
1.2. Nicht einzutreten ist dagegen auf die subsidiäre Verfassungsbeschwerde, da ihr vorliegend keine selbständige Bedeutung zukommt (vgl. Urteil 2C_1194/2012 vom 31. Mai 2013 E. 2.1 mit Hinweisen) : Sie bezieht sich ebenfalls auf den Familiennachzug, wobei der Beschwerdeführer eine Anspruchsbewilligung geltend macht und die von ihm erhobenen Rügen im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten geprüft werden.
1.3. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280 mit Hinweis). Hinsichtlich der Verletzung von Grundrechten, darin eingeschlossen solcher, die sich aus Völkerrecht ergeben, gilt eine qualifizierte Rügepflicht (<ref-law>; <ref-ruling> E. 2 S. 76 f.; <ref-ruling> E. 5.2 S. 373, 274 E. 1.6 S. 280 f.).
1.4. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (<ref-law>; <ref-ruling> E. 1.6 S. 280 f.; Urteil 2C_300/2013 vom 21. Juni 2013 E. 2.1). Die betroffene Person muss rechtsgenügend dartun, dass und inwiefern der festgestellte Sachverhalt in diesem Sinne mangelhaft erscheint und die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 i.V.m. Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.; <ref-ruling> E. 1.3 S. 351 f.). Rein appellatorische Kritik an der Sachverhaltsermittlung und an der Beweiswürdigung genügt den Begründungs- bzw. Rügeanforderungen nicht (<ref-ruling> E. 3 S. 104 f.).
1.5. Abzustellen ist auf den Sachverhalt zum Zeitpunkt des vorinstanzlichen Entscheids; nachträglich eingetretene Tatsachen und entsprechende Beweismittel ("echte Noven") bleiben damit im bundesgerichtlichen Verfahren unberücksichtigt (<ref-law>; <ref-ruling> E. 3.5 S. 397; <ref-ruling> E. 5.2.4 S. 229; <ref-ruling> E. 2.1 S. 343 f.; vgl. ferner Urteil 2C_683/2012 vom 19. März 2013 E. 3.3).
2.
2.1. Der Beschwerdeführer rügt zunächst eine offensichtlich falsche Sachverhaltsfeststellung der Vorinstanz. Dabei liegt insoweit unzulässige appellatorische Kritik vor, als der Beschwerdeführer über weite Strecken seine Sicht der Dinge wiederholt, ohne klar und deutlich darzulegen, inwiefern die vorinstanzliche Sachverhaltsfeststellung im Ergebnis offensichtlich unrichtig bzw. willkürlich sein soll (vgl. Urteil 2C_300/2013 vom 21. Juni 2013 E. 2.2).
2.2. Unbegründet ist der Vorwurf, die Vorinstanz habe die Tatsachen nach der Eheschliessung ausser Acht gelassen. Das Verwaltungsgericht hat - wie bereits die Rekursinstanz - den Umstand der Eheschliessung ausdrücklich berücksichtigt. Nicht offensichtlich unhaltbar ist die vorinstanzliche Beweiswürdigung, wonach die vom Beschwerdeführer aufgelegten Fotos und die Videosequenz keinen Beweis für eine "echte Ehe" darstellen, sondern bloss zeigen, dass sich der Beschwerdeführer im Kosovo aufgehalten hat. Als unzulässige echte Noven (<ref-law>) unberücksichtigt bleiben die im bundesgerichtlichen Verfahren eingereichten Unterlagen (Flugtickets, Fotos).
3.
3.1. Gemäss Art. 51 Abs. 1 lit. a AuG erlöschen die Ansprüche nach Art. 42 AuG, wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen. Erfasst wird davon die sog. Schein- oder Ausländerrechtsehe. Ihr Vorliegen darf nicht leichthin angenommen werden und ist nicht bereits dann gegeben, wenn ausländerrechtliche Motive für den Eheschluss mitentscheidend waren (vgl. <ref-ruling> E. 2.2 S. 151). Ein Bewilligungsanspruch entfällt vielmehr erst dann, wenn die Ehe einzig geschlossen wird, um die ausländerrechtlichen Bestimmungen zu umgehen, indem zumindest einer der Ehegatten nie eine dauerhafte Lebensgemeinschaft begründen wollte (<ref-ruling> E. 4a S. 55; <ref-ruling> E. 2 S. 294 ff.; <ref-ruling> E. 2 S. 2 ff.; Urteil 2C_177/2013 vom 6. Juni 2013 E. 3.2).
3.2. Ob eine Scheinehe vorliegt, entzieht sich regelmässig einem direkten Beweis und ist bloss durch Indizien zu erstellen. Feststellungen des kantonalen Gerichts über das Bestehen von solchen Indizien können äussere Gegebenheiten, aber auch innere psychische Vorgänge betreffen (Wille der Ehegatten). In beiden Fällen handelt es sich um tatsächliche Feststellungen, die für das Bundesgericht grundsätzlich verbindlich sind (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG; Urteil 2C_545/2012 vom 22. Februar 2013 E. 2.2 mit Hinweisen). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung migrationsrechtlicher Vorschriften (<ref-ruling> E. 2.3 S. 152 mit Hinweisen; Urteile 2C_177/2013 vom 6. Juni 2013 E. 3.5; 2C_12/2013 vom 1. Februar 2013 E. 2.1).
3.3. Für die Annahme einer Scheinehe bedarf es konkreter Hinweise darauf, dass die Ehegatten nicht eine eigentliche Lebensgemeinschaft führen wollen, sondern die Ehe nur aus ausländerrechtlichen Überlegungen geschlossen haben. Zu diesen Indizien zählen namentlich folgende Umstände: die Tatsache, dass die nachzuziehende Person von einer Wegweisung bedroht ist oder ohne Heirat keine Aufenthaltsbewilligung erlangen kann; das Vorliegen eines erheblichen Altersunterschieds zwischen den Ehegatten; die Umstände des Kennenlernens und der Beziehung, so etwa eine kurze Bekanntschaft vor der Heirat oder geringe Kenntnisse eines Ehegatten über den anderen; die Vereinbarung einer Bezahlung für die Heirat; die Tatsache, dass die Ehegatten nie eine Wohngemeinschaft aufgenommen haben (<ref-ruling> E. 3.1 S. 152; <ref-ruling> E. 2b S. 295; <ref-ruling> E. 3b S. 101 f.; <ref-ruling> E. 2b S. 3; <ref-ruling> E. 4b S. 420; Urteil 2C_177/2013 vom 6. Juni 2013 E. 3.3 mit Hinweisen).
3.4. Lässt die Indizienlage keinen klaren und unzweideutigen Schluss zu, ist das Vorliegen einer Scheinehe nicht erstellt. In diesem Fall ist dem ausländischen Ehegatten trotz allenfalls bestehender Zweifel die Aufenthaltsbewilligung zu erteilen, auf das Risiko hin, dass sich die Ehe aufgrund des späteren Verhaltens der Beteiligten (z.B. fehlendes eheliches Zusammenleben in der Schweiz) in Verbindung mit den bereits heute bekannten, in diese Richtung weisenden Indizien als Scheinehe herausstellt und die Aufenthaltsbewilligung gestützt auf die dannzumaligen Erkenntnisse widerrufen werden muss bzw. nicht mehr zu verlängern ist (Urteile 2C_400/2011 vom 2. Dezember 2011 E. 3.1; 2C_362/2010 vom 21. September 2010 E. 2.3.3; 2C_473/2008 vom 17. November 2008 E. 2.1; 2C_750/2007 vom 8. April 2008 E. 2.2; 2C_435/2007 vom 10. März 2008 E. 2.2). Hatten die Ehegatten noch gar keine Gelegenheit, die Absicht der Begründung einer Lebensgemeinschaft durch Zusammenleben unter Beweis zu stellen, ist dies gebührend zu berücksichtigen (vgl. Urteil 2C_177/2013 vom 6. Juni 2013 E. 3.4), schliesst jedoch nicht aus, dass - bei entsprechender Indizienlage - bereits im Zeitpunkt der erstmaligen Gesuchseinreichung auf eine Scheinehe geschlossen werden darf und die Erteilung einer fremdenpolizeilichen Nachzugsbewilligung von Anfang an zu verweigern ist (Urteile 2C_125/2011 vom 31. August 2011 E. 3.5; 2C_222/2008 vom 31. Oktober 2008 E. 3.4; 2C_750/2007 vom 8. April 2008 E. 2.2; 2C_435/2007 vom 10. März 2008 E. 2.2).
3.5. Von der ausländerrechtlichen Beurteilung zu unterscheiden ist die Aufgabe des Zivilstandsbeamten, Umgehungen des Ausländerrechts entgegenzutreten und bei offensichtlichem Missbrauch die Mitwirkung an der Eheschliessung zu verweigern (vgl. <ref-law>; Urteil 5A_901/2012 vom 23. Januar 2013 E. 4.2.1 mit Hinweisen). Der Zivilstandsbeamte nimmt die Prüfung der Migrationsbehörden nicht vorweg; diese entscheiden frei über die Erteilung oder Verweigerung der Aufenthaltsbewilligung an einen ausländischen Ehegatten. Ausländerrechtliche Massnahmen sind damit unabhängig vom rechtlichen Bestand der Ehe möglich ( MICHEL MONTINI, in: Basler Kommentar, ZGB I, 4. Aufl. 2010, N. 3 und 13 zu <ref-law>; Botschaft vom 8. März 2002 zum Bundesgesetz über die Ausländerinnen und Ausländer, BBl 2002 3709, 3837 zu Art. 97a E-ZGB; Ziff. 6.13.2.2 lit. c der Weisungen des BFM zum Ausländerbereich, Familiennachzug [Stand: 1. Juli 2013], abrufbar unter www.bfm.admin.ch).
4.
4.1. Der vorinstanzliche Schluss auf eine Scheinehe ist entgegen den Vorbringen des Beschwerdeführers nachvollziehbar begründet. Dabei sticht besonders der zeitliche Ablauf der Ereignisse hervor. Die Eheleute haben ihren Entschluss zur Eheschliessung nach ihrer eigenen Schilderung nur wenige Wochen nach der ersten (telefonischen) Kontaktaufnahme gefällt, und zwar am Tag, nachdem sie erstmals über Video-Chat miteinander kommuniziert hatten. Weniger als ein halbes Jahr später und noch vor der ersten persönlichen Begegnung stellte A._ ein Gesuch um Einreise zur Ehevorbereitung. Kurze Zeit nach der Abweisung des erstinstanzlichen Gesuchs erfolgte die Heirat im Kosovo. Willkürfrei würdigte die Vorinstanz den Umstand, dass der Beschwerdeführer erst für die Hochzeit in den Kosovo reiste, als Hinweis dafür, wie wenig dem Beschwerdeführer daran gelegen war, die Ehefrau persönlich kennenzulernen.
4.2. Die aus dem zeitlichen Ablauf zu ziehenden Schlüsse werden durch die übrigen, von der Vorinstanz einlässlich dargestellten Indizien bekräftigt. Die Eheleute weisen einen Altersunterschied von über 20 Jahren auf, äusserten sich widersprüchlich und unklar zu den Umständen ihres Kennenlernens und hatten nur geringfügige Kenntnisse voneinander. Entgegen der Auffassung des Beschwerdeführers werden die aus dieser Indizienlage gezogenen Schlüsse durch die Tatsache der Heirat nicht "gegenstandslos", sondern sind für das Prüfen des Anspruchs auf Familiennachzug (Art. 42 AuG) rechtserheblich. Eine unzulässige Beweislastumkehr kann darin nicht erblickt werden. Keine entscheidende Bedeutung kommt dem Umstand zu, dass das Zivilstandsamt der Stadt Zürich nach Prüfung des Sachverhalts das Ehevorbereitungsverfahren durchgeführt hat. Das Migrationsamt des Kantons Zürich war dadurch nicht gebunden, sondern hatte den Sachverhalt eigenständig zu prüfen.
4.3. Liegt eine Scheinehe vor, hat die Vorinstanz zu Recht einen Anspruch auf Familiennachzug verneint (Art. 42 i.V.m. Art. 51 Abs. 1 lit. a AuG). Es liegt gar keine Familien- bzw. Ehegemeinschaft vor. Unter diesen Umständen "erlischt" der Anspruch nach Art. 42 AuG ohne weitere Interessenabwägung, zumal es an einem effektiven, d.h. intakten und tatsächlich gelebten Familien- bzw. Eheleben mangelt und daher die Garantie auf Achtung des Familienlebens (Art. 8 EMRK; <ref-law>) nicht angerufen werden kann (<ref-ruling> E. 3a S. 21; <ref-ruling> E. 4b S. 152; Urteil 2C_3/2012 vom 15. August 2012 E. 4.5; vgl. ferner Urteil 2C_1170/2012 vom 24. Mai 2013 E. 3.2 mit Hinweisen). Andere Gründe für eine Anspruchsbewilligung sind weder ersichtlich noch dargetan.
5.
5.1. Aus den vorstehenden Erwägungen ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten unbegründet ist. Da die Gewinnaussichten der Prozessbegehren von Anfang an beträchtlich geringer waren als die Verlustgefahren, erweist sich die Beschwerde als aussichtslos und das Gesuch um unentgeltliche Rechtspflege ist abzuweisen (<ref-law>; <ref-ruling> E. 2.3.1 S. 135 f.; Urteil 2C_856/2012 vom 25. März 2013 E. 7.1). Dem Verfahrensausgang entsprechend wird der unterliegende Beschwerdeführer kostenpflichtig (<ref-law>). Es sind keine Parteientschädigungen geschuldet (<ref-law>).
5.2. Zum Kostenpunkt des vorinstanzlichen Entscheids, namentlich zur Abweisung der unentgeltlichen Rechtspflege im vorinstanzlichen Verfahren, äussert sich der Beschwerdeführer in seiner Rechtsschrift nicht substanziiert, namentlich stellt er keinen ausdrücklichen Antrag und erhebt keine Rügen, weshalb darauf nicht einzugehen ist (Art. 42 und <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2.
Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
4.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 29. August 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Egli