Sachverhalt: A. A.a. A._, geboren 1962, arbeitet seit 1. Juli 1988 in Betrieben des Eidg. Departementes für Verteidigung, Bevölkerungsschutz und Sport (VBS), gemäss öffentlich-rechtlichem Arbeitsvertrag vom 8./20. Februar 2006 (nachfolgend: Arbeitsvertrag) seit 1. Februar 2006 in der Funktion als Chef Mittlere und Kleinobjekte der Logistikbasis der Armee (Arbeitgeberin). Es handelt sich dabei um eine Funktion mit besonderer Sicherheitsempfindlichkeit, für welche die periodische Durchführung einer Personensicherheitsprüfung vorgesehen ist. Die dafür zuständige Fachstelle für Personensicherheitsprüfungen im Bereich Informations- und Objektsicherheit (Fachstelle IOS) des VBS erliess am 3. November 2011 unter anderem aufgrund der zwischenzeitlich erlangten Kenntnis von einer rechtskräftigen Verurteilung wegen Pornografie eine negative Risikoverfügung, wonach A._ als Sicherheitsrisiko erachtet und unter anderem empfohlen wurde, von seiner Weiterverwendung in der Funktion als Chef Mittlere und Kleinobjekte bei der Logistikbasis der Armee sei abzusehen; zudem dürfe ihm kein Zugang mehr zu vertraulich und geheim klassifizierten Informationen, Materialien und militärischen Anlagen mit Schutzzonen 2 und 3 gewährt werden. Das Bundesgericht bestätigte den diese Verfügung vom 3. November 2011 schützenden Entscheid des Bundesverwaltungsgerichts mit Urteil 8C_683/2012 vom 4. März 2013. A.b. Nachdem die Fachstelle IOS der Arbeitgeberin mit Zwischenverfügung vom 14. Juli 2011 empfohlen hatte, A._ bis zum Abschluss der Personensicherheitsprüfung keinen Zugang mehr zu vertraulich oder geheim klassifizierten Informationen, Materialien und militärischen Anlagen mit Schutzzonen 2 und 3 zu gewähren, stellte die Arbeitgeberin ihn bis auf Weiteres vom Dienst frei, untersagte ihm den Zutritt zum Arbeitsplatz und entzog einer allfälligen Beschwerde die aufschiebende Wirkung (Verfügung vom 31. August 2011). Auf Beschwerde hin schützten diese Verfügung zunächst das VBS und sodann mit rechtskräftigem Entscheid A-372/2012 vom 25. Mai 2012 auch das Bundesverwaltungsgericht. A.c. Am 1. Dezember 2011 verfügte die Arbeitgeberin die fristlose Auflösung des Arbeitsverhältnisses. Auf Beschwerde hin hob das VBS diese Verfügung auf und stellte fest, das Arbeitsverhältnis werde per 31. August 2012 aufgelöst und bis zu diesem Zeitpunkt der Lohn ausgerichtet; einer allfälligen Beschwerde gegen diesen Entscheid entzog das VBS die aufschiebende Wirkung (Entscheid vom 23. August 2012). B. Die hiegegen erhobene Beschwerde des A._ hiess das Bundesverwaltungsgericht mit Entscheid A-4973/2012 vom 5. Juni 2013 im Sinne der Erwägungen gut, hob den angefochtenen Entscheid des VBS vom 23. August 2012 auf und stellte die Nichtigkeit der Kündigung fest. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt das VBS die Aufhebung des angefochtenen Gerichtsentscheids. Während A._ auf Abweisung der Beschwerde schliesst, verzichtet das Bundesverwaltungsgericht auf eine Vernehmlassung.