You may Flatten
the list and then take a RandomSample
before partitioning to the original dimensions with Length
and TakeList
.
With keys
the list in the OP then
TakeList[RandomSample[Flatten@keys,TakeList[RandomSample All]@ Flatten @ keys, Length /@ keys]
Hope this helps.