Accesing keys based on position in an association

I would like to have the following simple function GetKey[] on a very large association.

(* The actual Association is very large, this is just small example *) 
assoc = <|{1,1} -> 2, {1,2} -> 3, {2,1}->4, {2,2}->5|>;
GetKey[assoc, 1]
GetKey[assoc, 4]


(* output *) 
{1,1}
{2,2}

That is, I want to access keys based on their position in the association. Any way this can be done efficiently for a large association? I know one can use the Keys[assoc][[position]] function but this is too slow for a large association.

EDIT: Based on the comments below I am giving you the timing information for the function I know that does the job.

a = 1024*1024;
keys = Table[i, {i, a}];
values = RandomReal[{0, 1000000}, {a}];
assoc = Association[MapThread[Rule, {keys, values}]];

AbsoluteTiming[k = Keys[assoc][[10000]];]

(* output *)
{0.548738, Null}

This is too slow for say a hundred thousand accesses.

Answer

Perhaps:

GetKey[assoc_, index_] := First @ Keys @ Take[assoc, {index}]

Your first example:

assoc = <|{1,1} -> 2, {1,2} -> 3, {2,1}->4, {2,2}->5|>;

GetKey[assoc, 1]
GetKey[assoc, 4]

{1, 1}

{2, 2}

Your large example:

a = 1024*1024;
keys = Table[i, {i, a}];
values = RandomReal[{0, 1000000}, {a}];
assoc = Association[MapThread[Rule, {keys, values}]];

AbsoluteTiming[Keys[assoc][[10000]]]
AbsoluteTiming[GetKey[assoc, 10000]] 

{0.373301, 10000}

{0.003779, 10000}