Connected Board Column => Very slow (Contact & Company with over 6000 contacts)

We have a board with contacts (about 6000 entries) and one with companies (about 2500 entries). When I want to view or change my contacts in the company board, is very slow. Sometimes it takes up to 15 seconds until the window opens. It is very tedious to work like this. Who has tips on how to get around this?