The Star Key is available in Chapter 6 in Angela's Bar in Vedan. This is available right after Deego joins your group, so I'm guessing you've been without this one for a while
. Since the bar gets destroyed you have to wait till it is rebuilt, I guess, to get it again (one of the FAQ's says Chapter 8).
The Sun Key is available in Chapter 10 in a house in Johannasburg (on Rosa). Maybe you haven't gotten there yet.