Faits : A. Le 2 février 2011, le Conseil fédéral a adopté l'ordonnance instituant des mesures à l'encontre de certaines personnes originaires de la République arabe d'Egypte (ci-après: Ordonnance-Egypte ou O-Egypte; RS 946.231.132.1). Le nom de X._ figure sur l'annexe à cette ordonnance avec l'indication: "ancien Secrétaire de l'Organisation au Partie national démocratique" (sic). Le 14 février 2011, la banque A._ SA a informé la Direction du droit international public du Département fédéral des affaires étrangères (ci-après: le Département fédéral) que X._ était l'ayant droit économique de plusieurs comptes auprès de son établissement dont l'un présentait un solde de 1'228'357 fr. (compte n° 1) et l'autre de 30'962'682 fr. (compte n° 2), étant précisé que la société B._ Holdings Ltd était la titulaire du second compte. Le 17 février 2011, la banque C._ SA a annoncé deux relations bancaires avec X._ présentant un solde de USD 9'254.-. Le 4 mars 2011, X._ a contesté son inscription sur l'annexe de l'ordonnance du 2 février 2011, puis a demandé la libération d'un montant de 200'000 fr. du compte n° 2. Cette demande a été rejetée par décision du 27 avril 2011, qui n'a pas fait l'objet de recours. Le 9 janvier 2012, le Ministère public de la Confédération a admis une demande d'entraide judiciaire formée par les autorités égyptiennes et, le 10 février 2012, il a étendu à X._ une instruction pénale ouverte contre plusieurs personnes proches du clan de l'ancien président égyptien Hosni Mubarak. Le même jour, il a ordonné à A._ SA de bloquer le compte n° 1 ap partenant à celui-ci et, le 5 avril 2012, il a fait séquestrer ledit compte. B. Le 13 août 2012, le Département fédéral a rejeté la requête de X._, formée le 6 juillet 2011 et complétée le 13 février 2012, tendant à sa radiation de l'Ordonnance-Egypte et à la levée du blocage de ses avoirs. Il a considéré en substance que l'inscription sur l'annexe à cette ordonnance ne s'avérait ni arbitraire ni contraire au principe de la proportionnalité, X._ ayant été condamné, en septembre 2011, à dix ans de prison et à 660 millions de livres égyptiennes d'amende pour avoir obtenu de manière irrégulière des licences pour deux de ses sociétés. En outre, l'intéressé faisait l'objet d'une instruction pénale en Suisse et était également désigné par l'Union européenne parmi les personnes faisant l'objet de mesures restrictives en lien avec la situation en Egypte. Par arrêt du 5 décembre 2013, le Tribunal administratif fédéral a rejeté le recours de X._ à l'encontre de la décision du Département fédéral du 13 août 2012. C. A l'encontre de l'arrêt du 5 décembre 2013, X._ dépose un recours en matière de droit public au Tribunal fédéral. Il conclut, avec suite de frais et dépens, à l'annulation de l'arrêt entrepris et de la décision du 13 août 2012 du Département fédéral; i l demande à être radié de la liste des personnes visées par l'annexe de l'Ordonnance-Egypte. A titre subsidiaire, il requiert qu'il soit ordonné au Département fédéral de rendre une nouvelle décision ayant pour objet de le radier de la liste des personnes visées par l'Ordonnance-Egypte. Le Tribunal administratif fédéral a renoncé à prendre position. Au terme de ses déterminations, la Confédération suisse, agissant par l'entremise du Département fédéral, propose le rejet du recours dans la mesure de sa recevabilité et la confirmation de l'arrêt du 5 décembre 2013. X._ a formulé des observations finales. Par ordonnance du 17 février 2014, le Tribunal fédéral a admis la demande du recourant tendant à la réduction du montant de l'avance de frais initialement fixée. 