Navigating Slack efficiently is not as bad as I thought.
I already knew about Ctrl+K to jump to a channel or chat, and about Ctrl+F for search. But something still felt off: jumping between chats was more awkward then I expect.
Now I discovered these subtle buttons:

And they even inform me that I can use Alt+← resp. Alt+→ to navigate through my history — neat!