diff --git a/app/models/loose_foreign_keys/deleted_record.rb b/app/models/loose_foreign_keys/deleted_record.rb
index 0fbdd2d8a5b971eefb031740639e1ac791c251de..db82d5bbf292f4a3c811894064a153b4d0309280 100644
--- a/app/models/loose_foreign_keys/deleted_record.rb
+++ b/app/models/loose_foreign_keys/deleted_record.rb
@@ -1,6 +1,6 @@
 # frozen_string_literal: true
 
-class LooseForeignKeys::DeletedRecord < ApplicationRecord
+class LooseForeignKeys::DeletedRecord < Gitlab::Database::SharedModel
   PARTITION_DURATION = 1.day
 
   include PartitionedTable
diff --git a/app/models/loose_foreign_keys/modification_tracker.rb b/app/models/loose_foreign_keys/modification_tracker.rb
index 6eb04608cd94eb3ab877ee208962f4b8ebf44792..72a596d2114b52dd4747b9479b3eeb5fa8d88f43 100644
--- a/app/models/loose_foreign_keys/modification_tracker.rb
+++ b/app/models/loose_foreign_keys/modification_tracker.rb
@@ -4,7 +4,7 @@ module LooseForeignKeys
   class ModificationTracker
     MAX_DELETES = 100_000
     MAX_UPDATES = 50_000
-    MAX_RUNTIME = 3.minutes
+    MAX_RUNTIME = 30.seconds # must be less than the scheduling frequency of the LooseForeignKeys::CleanupWorker cron worker
 
     delegate :monotonic_time, to: :'Gitlab::Metrics::System'
 
diff --git a/app/services/loose_foreign_keys/process_deleted_records_service.rb b/app/services/loose_foreign_keys/process_deleted_records_service.rb
index 025829aa774f29c69c7cb3f1c63be8df0ff00989..2826bdb4c3ce139607b57946dc6c6999f171b717 100644
--- a/app/services/loose_foreign_keys/process_deleted_records_service.rb
+++ b/app/services/loose_foreign_keys/process_deleted_records_service.rb
@@ -10,7 +10,6 @@ def initialize(connection:)
 
     def execute
       modification_tracker = ModificationTracker.new
-
       tracked_tables.cycle do |table|
         records = load_batch_for_table(table)
 
diff --git a/app/workers/loose_foreign_keys/cleanup_worker.rb b/app/workers/loose_foreign_keys/cleanup_worker.rb
index b4565dbf6244d32fec93501644d7f06b55586f20..c3492fed77bddbaf87ec42eb67c1ef33b1d6d8e1 100644
--- a/app/workers/loose_foreign_keys/cleanup_worker.rb
+++ b/app/workers/loose_foreign_keys/cleanup_worker.rb
@@ -6,6 +6,7 @@ class CleanupWorker
     include Gitlab::ExclusiveLeaseHelpers
     include CronjobQueue # rubocop: disable Scalability/CronWorkerContext
 
+    sidekiq_options retry: false
     feature_category :sharding
     data_consistency :always
     idempotent!
@@ -13,13 +14,30 @@ class CleanupWorker
     def perform
       return if Feature.disabled?(:loose_foreign_key_cleanup, default_enabled: :yaml)
 
-      ttl = ModificationTracker::MAX_RUNTIME + 1.minute
-      in_lock(self.class.name.underscore, ttl: ttl, retries: 0) do
-        # TODO: Iterate over the connections
-        # https://gitlab.com/gitlab-org/gitlab/-/issues/341513
-        stats = ProcessDeletedRecordsService.new(connection: ApplicationRecord.connection).execute
+      in_lock(self.class.name.underscore, ttl: ModificationTracker::MAX_RUNTIME, retries: 0) do
+        stats = {}
+
+        connection_name, base_model = current_connection_name_and_base_model
+
+        Gitlab::Database::SharedModel.using_connection(base_model.connection) do
+          stats = ProcessDeletedRecordsService.new(connection: base_model.connection).execute
+          stats[:connection] = connection_name
+        end
+
         log_extra_metadata_on_done(:stats, stats)
       end
     end
+
+    private
+
+    # Rotate the databases every minute
+    #
+    # If one DB is configured: every minute use the configured DB
+    # If two DBs are configured (Main, CI): minute 1 -> Main, minute 2 -> CI
+    def current_connection_name_and_base_model
+      minutes_since_epoch = Time.current.to_i / 60
+      connections_with_name = Gitlab::Database.database_base_models.to_a # this will never be empty
+      connections_with_name[minutes_since_epoch % connections_with_name.count]
+    end
   end
 end
diff --git a/config/initializers/1_settings.rb b/config/initializers/1_settings.rb
index ca5d133381c9e5946d33695a9f9db65b290747fb..8244f570a18903db49f4bb5c3664b92bcbcea255 100644
--- a/config/initializers/1_settings.rb
+++ b/config/initializers/1_settings.rb
@@ -735,7 +735,7 @@
   Settings.cron_jobs['app_sec_dast_profile_schedule_worker']['cron'] ||= '7-59/15 * * * *'
   Settings.cron_jobs['app_sec_dast_profile_schedule_worker']['job_class'] = 'AppSec::Dast::ProfileScheduleWorker'
   Settings.cron_jobs['loose_foreign_keys_cleanup_worker'] ||= Settingslogic.new({})
-  Settings.cron_jobs['loose_foreign_keys_cleanup_worker']['cron'] ||= '*/5 * * * *'
+  Settings.cron_jobs['loose_foreign_keys_cleanup_worker']['cron'] ||= '*/1 * * * *'
   Settings.cron_jobs['loose_foreign_keys_cleanup_worker']['job_class'] = 'LooseForeignKeys::CleanupWorker'
 end
 
diff --git a/doc/development/database/loose_foreign_keys.md b/doc/development/database/loose_foreign_keys.md
index ec2c41220819a550f1944adee1ad86f7b7750ad3..97d150b1a18ab66bf5877d7d0f9582c81f8b850b 100644
--- a/doc/development/database/loose_foreign_keys.md
+++ b/doc/development/database/loose_foreign_keys.md
@@ -43,7 +43,7 @@ we can:
 
 1. Create a `DELETE` trigger on the `projects` table.
    Record the deletions in a separate table (`deleted_records`).
-1. A job checks the `deleted_records` table every 5 minutes.
+1. A job checks the `deleted_records` table every minute or two.
 1. For each record in the table, delete the associated `ci_pipelines` records
    using the `project_id` column.
 
diff --git a/spec/workers/loose_foreign_keys/cleanup_worker_spec.rb b/spec/workers/loose_foreign_keys/cleanup_worker_spec.rb
index 3c628d036ff8b3b500c9d7ab3d9f0e7f55ffedc5..497f95cf34de70ba13bd645b57f68d6817aaa073 100644
--- a/spec/workers/loose_foreign_keys/cleanup_worker_spec.rb
+++ b/spec/workers/loose_foreign_keys/cleanup_worker_spec.rb
@@ -4,6 +4,7 @@
 
 RSpec.describe LooseForeignKeys::CleanupWorker do
   include MigrationsHelpers
+  using RSpec::Parameterized::TableSyntax
 
   def create_table_structure
     migration = ActiveRecord::Migration.new.extend(Gitlab::Database::MigrationHelpers::LooseForeignKeyHelpers)
@@ -149,4 +150,31 @@ def count_deletable_rows
       expect { described_class.new.perform }.not_to change { LooseForeignKeys::DeletedRecord.status_processed.count }
     end
   end
+
+  describe 'multi-database support' do
+    where(:current_minute, :configured_base_models, :expected_connection) do
+      2 | { main: ApplicationRecord, ci: Ci::ApplicationRecord } | ApplicationRecord.connection
+      3 | { main: ApplicationRecord, ci: Ci::ApplicationRecord } | Ci::ApplicationRecord.connection
+      2 | { main: ApplicationRecord } | ApplicationRecord.connection
+      3 | { main: ApplicationRecord } | ApplicationRecord.connection
+    end
+
+    with_them do
+      before do
+        allow(Gitlab::Database).to receive(:database_base_models).and_return(configured_base_models)
+      end
+
+      it 'uses the correct connection' do
+        LooseForeignKeys::DeletedRecord.count.times do
+          expect_next_found_instance_of(LooseForeignKeys::DeletedRecord) do |instance|
+            expect(instance.class.connection).to eq(expected_connection)
+          end
+        end
+
+        travel_to DateTime.new(2019, 1, 1, 10, current_minute) do
+          described_class.new.perform
+        end
+      end
+    end
+  end
 end