What is the most efficient way to make a Locality Entity (Town, City, Village etc) with a Country Entity?
In Relational Database terms efficiency revolves around avoiding the duplication of data.  The 3 tables that you show in your question seem reasonable provided:


You can have a Locality without having a Country
You can have a Country without having a Locality


This is actually quite a viable design, since in some parts of the world they may not define locations as you describe.  (There are a lot of unique decisions made around the planet.) Of course you can generate an artificial name or  description for your tracking purpose should that be necessary.

For example: There is no named locality, you could create a Locality like: "Island NW of Salty Creek"

If you intend for each Locality to belong to a single Country then you might benefit from a small change to add a CountryLocality table:

Locality


PK UN LocalityID
UN LocalityName


Country


PK UN CountryID
UN CountryName


CountryLocality


PK UN CountryLocalityID
FK    CountryID
FK    LocalityID


UserProfile


Username...Password...etc
FK    CountryLocalityID


This is definitely a design and usage issue for you to decide on since the CountryLocality table adds some overhead. It depends on how strong the Country-Locality connection should be and whether this extra step is worth it for your application.