Faits : A. D.X._ (1950) est décédé le 3 mars 2013, laissant comme héritiers légaux ses deux enfants, A.X._ (1982) et B.X._ (1985). A.a. Le défunt a laissé deux dispositions testamentaires olographes, rédigées le 29 décembre 2012 : Par un premier testament, il a institué pour seuls héritiers ses deux enfants, A.X._ et B.X._. Il a en outre confirmé que tous les biens qui étaient au nom de sa compagne depuis plusieurs années, C._, suite à des répartitions ou des donations réalisées de son plein gré, appartenaient à celle-ci, en sorte que ses héritiers n'avaient aucune prétention envers celle-ci à quelque titre que ce soit. Dans le second testament, le disposant a souhaité régler exclusivement le sort de sa propriété "...", à F._ (Genève). Il a institué comme héritiers de cet immeuble, à parts égales d'une demie chacun, ses deux enfants. Le testateur a autorisé ses enfants à vendre l'immeuble, dans un délai et aux conditions déterminés par sa compagne, C._, laquelle est autorisée à résider au "..." le temps qui lui plaira. Le testateur a désigné sa compagne comme exécutrice testamentaire des présentes dispositions à cause de mort, avec le pouvoir de gérer et d'administrer l'immeuble, y compris de procéder au paiement des frais et dépenses y relatives au moyen du compte bancaire utilisé à cet effet jusqu'à présent, le pouvoir de procéder à la vente de l'immeuble et au partage du produit de la vente entre les héritiers, ainsi que le pouvoir de représenter l'hoirie à l'égard des banques et des autorités administratives. Le disposant a requis que l'institution d'exécutrice testamentaire soit mentionnée au Registre foncier. A.b. Une attestation d'exécutrice testamentaire a été délivrée à C._ par le Juge de paix le 3 avril 2013, concernant uniquement la propriété "...". A.c. Pour donner suite à la requête du 12 avril 2013 des héritiers, un inventaire civil des biens se trouvant dans les immeubles situés sis à n° s xx-xy, route de F._, a été ordonné le 15 avril 2013. Le 26 avril 2013, en raison de difficultés rencontrées par le notaire mandaté pour établir cet inventaire pour exercer sa mission, le Juge de paix a attiré l'attention de l'exécutrice testamentaire sur son devoir de collaboration, sur l'interdiction de soustraire des biens à l'inventaire et sur son obligation de défendre les intérêts de l'hoirie et non pas les siens propres. A.d. Par ordonnance du 24 mai 2013, le Tribunal civil a notamment fait interdiction à C._ d'entraver de quelque manière que ce soit l'accès de B.X._ à son logement sis à n° xx, route de F._. B. Par requête du 10 mai 2013 auprès du Juge de paix, les héritiers ont conclu à la destitution de l'exécutrice testamentaire et, à titre provisoire, à la suspension provisoire de ses pouvoirs, avec notification au Registre foncier. Ils lui reprochaient d'entraver l'établissement d'un inventaire successoral ainsi que l'inventaire conservatoire ordonné le 15 avril 2013, d'avoir soustrait et dissimulé les actifs successoraux, d'avoir abusé de son pouvoir en ne laissant pas B.X._ entrer à son domicile, et d'avoir tenté de faire signer aux héritiers des conventions aux fins de s'approprier des biens du défunt. Par ordonnance du 16 mai 2013, le Juge de paix a précisé la mission d'exécution testamentaire confiée à la compagne du défunt, limitée à la gestion et l'administration de l'immeuble sis n° xy, route de F._, déclaré nulle et de nul effet l'attestation délivrée le 3 avril 2013, prié le Registre foncier d'en prendre acte, invité l'exécutrice testamentaire à restituer ladite attestation et à laisser un libre accès au notaire et aux héritiers aux fins de procéder à l'inventaire des immeubles situés n° xx, xy, route de F._, ainsi qu'à collaborer à l'établissement de l'inventaire en remettant tous les documents personnels du défunt nécessaires à cet effet. C._ a restitué l'attestation d'exécutrice testamentaire et contesté avoir entravé le processus d'inventaire. Par convention de partage partiel du 23 mai 2013, les deux héritiers légaux ont convenu du partage entre eux de divers biens, singulièrement du domaine "...", en adoptant pour les immeubles le régime de la copropriété pour une demie chacun, à titre de partage définitif entre eux. B.a. Par deux compléments des 6 et 7 juin 2013 à la requête de destitution du 10 mai 2013, les héritiers ont conclu notamment à ce qu'il soit constaté que la mission de l'exécutrice testamentaire était terminée dans la mesure du partage de la succession et de la délivrance du legs d'habitation en faveur de celle-ci. La compagne du défunt a conclu à ce qu'il lui soit donné acte de ce qu'elle s'était intégralement conformée à l'ordonnance du 16 mai 2013 et à ce que les héritiers soient déboutés de toutes leurs conclusions, y compris des requêtes complémentaires des 6 et 7 juin 2013. B.b. Par ordonnance du 25 juillet 2013, le Juge de paix a prié C._ de collaborer à l'inventaire des biens au jour du décès, de répondre aux questions du notaire chargé de dresser l'inventaire des immeubles sis n° s xx-xy, route de F._, constaté que les pouvoirs de l'exécutrice testamentaire, chargée de gérer et administrer le bien immobilier sis au n° xy, route de F._, avaient pris fin par le partage intervenu entre les héritiers, prié le Registre foncier d'en prendre acte, invité C._ à rendre des comptes de ses activités aux héritiers et à leur restituer tous les documents ayant appartenu au défunt. C._ a formé appel contre cette ordonnance le 12 août 2013, concluant à sa réforme en ce sens qu'elle devait être confirmée dans ses pouvoirs d'exécutrice testamentaire pour la propriété "...", et qu'une attestation d'exécutrice testamentaire devait lui être délivrée. Par décision du 27 août 2013, la Chambre civile de la Cour de justice a ordonné la suspension immédiate des pouvoirs de l'exécutrice testamentaire concernant l'immeuble sis n° xy, route de F._. B.c. Statuant par arrêt du 3 décembre 2013, la Chambre civile de la Cour de justice a annulé partiellement l'ordonnance querellée, au motif que le juge de paix était incompétent ratione loci. Cette décision a été annulée par arrêt du Tribunal fédéral du 19 mai 2014 (5A_55/2014), la cause étant renvoyée à l'autorité cantonale pour instruction et jugement, la compétence des autorités genevoises étant tenue pour acquise. Suite au renvoi, la compagne du défunt a confirmé ses conclusions d'appel du 12 août 2013 et les héritiers ont confirmé leurs conclusions, principalement, en révocation de l'exécutrice testamentaire, subsidiairement, en constatation que sa mission s'était achevée par le partage, invoquant des faits nouveaux survenus depuis le prononcé du précédent arrêt de la Cour de justice du 3 décembre 2013, constitutifs, selon eux, d'entrave à l'exécution de l'inventaire conservatoire, de faux et usage de faux en faisant fabriquer des factures d'oeuvres à son nom, dressées initialement aux noms du défunt ou de G._ SA, d'instigation à la dissimulation d'actifs successoraux, d'intimidation de témoins, et d'actes de contrainte tendant à empêcher les héritiers de disposer de biens dont la propriété est incontestée, par le biais d'agents de sécurité. Par arrêt du 18 septembre 2014, la Chambre de surveillance de la Cour de justice a retourné la procédure à la Justice de paix pour qu'elle se prononce sur la question de la destitution de l'exécutrice testamentaire. B.d. Par ordonnance du 10 avril 2015, le Juge de paix a révoqué C._ de ses fonctions d'exécutrice testamentaire de la succession de feu D.X._, déclarant l'ordonnance immédiatement exécutoire nonobstant recours. B.e. Sur appel formé le 27 avril 2015 par C._, la Chambre civile de la Cour de justice a, par arrêt du 7 décembre 2015, annulé l'ordonnance déférée et rejeté la requête en destitution de l'exécutrice testamentaire du 10 mai 2013, ainsi que ses compléments. C. Par acte du 22 janvier 2016, dont une version corrigée a été remise à la Poste suisse le 25 janvier 2016 et parvenue au Tribunal de céans le 26 janvier 2016, A.X._ et B.X._ exercent un recours en matière civile au Tribunal fédéral. Ils concluent à l'annulation de l'arrêt entrepris et, principalement, à sa réforme en ce sens que l'intimée est définitivement révoquée des pouvoirs d'exécutrice testamentaire et que l'attestation de la Justice de paix du 3 avril 2013 constatant la qualité d'exécutrice testamentaire est révoquée, subsidiairement, au renvoi de la cause aux autorités cantonales pour nouvelle décision. Au préalable, les recourants sollicitent l'octroi de l'effet suspensif à leur recours, en ce sens que les pouvoirs d'exécutrice testamentaire de l'intimée sont suspendus avec effet immédiat, jusqu'à droit jugé. Invitées à se déterminer sur la requête d'effet suspensif, l'intimée a conclu à son rejet et l'autorité précédente s'en est rapportée à justice. D. Par ordonnance du 11 février 2016, la Juge présidant la IIe Cour de droit civil du Tribunal fédéral a octroyé l'effet suspensif au recours, en ce sens que les pouvoirs d'exécutrice testamentaire de l'intimée concernant l'immeuble sis n° xy, route de F._ restent suspendus. Des réponses au fond n'ont pas été requises.