diff --git a/app/controllers/projects/deploy_keys_controller.rb b/app/controllers/projects/deploy_keys_controller.rb
index b5dd102df64a2b5313acf30de308b7bb78232fd4..8918baa041b5fc34e1174b8cb6cd7afc01978797 100644
--- a/app/controllers/projects/deploy_keys_controller.rb
+++ b/app/controllers/projects/deploy_keys_controller.rb
@@ -112,7 +112,8 @@ def create_params
     create_params = params.require(:deploy_key)
                           .permit(:key, :title, :expires_at, deploy_keys_projects_attributes: [:can_push])
     create_params.dig(:deploy_keys_projects_attributes, '0')&.merge!(project_id: @project.id)
-    create_params
+
+    create_params.merge(organization_id: @project.organization_id)
   end
 
   def update_params
diff --git a/app/controllers/user_settings/ssh_keys_controller.rb b/app/controllers/user_settings/ssh_keys_controller.rb
index a2dbbc49eefdd2be1119bf2a616097708df32f85..b54d0cc5ad438870815a0175f12df7bf40e5a580 100644
--- a/app/controllers/user_settings/ssh_keys_controller.rb
+++ b/app/controllers/user_settings/ssh_keys_controller.rb
@@ -16,7 +16,9 @@ def show
     end
 
     def create
-      @key = Keys::CreateService.new(current_user, key_params.merge(ip_address: request.remote_ip)).execute
+      @key = Keys::CreateService.new(current_user,
+        key_params.merge(ip_address: request.remote_ip,
+          organization: Current.organization)).execute
 
       if @key.persisted?
         redirect_to user_settings_ssh_key_path(@key)
diff --git a/app/models/key.rb b/app/models/key.rb
index 96220959d0c58cf623d5726011da1eed4c4304b1..78c4518b46c33196bf4964d6ce7c6e915a0ea776 100644
--- a/app/models/key.rb
+++ b/app/models/key.rb
@@ -12,6 +12,7 @@ class Key < ApplicationRecord
   sha256_attribute :fingerprint_sha256
 
   belongs_to :user
+  belongs_to :organization, class_name: 'Organizations::Organization'
 
   has_many :ssh_signatures, class_name: 'CommitSignatures::SshSignature'
 
diff --git a/app/services/deploy_keys/create_service.rb b/app/services/deploy_keys/create_service.rb
index 3245e749164cc2f7e0c43ed14e99bfd41630f343..c9cac07136f9b593654d716567fe9b76409628d2 100644
--- a/app/services/deploy_keys/create_service.rb
+++ b/app/services/deploy_keys/create_service.rb
@@ -3,7 +3,8 @@
 module DeployKeys
   class CreateService < Keys::BaseService
     def execute(project: nil)
-      DeployKey.create(params.merge(user: user))
+      organization = params[:organization] || user.organization
+      DeployKey.create(params.merge(user:, organization:))
     end
   end
 end
diff --git a/app/services/keys/create_service.rb b/app/services/keys/create_service.rb
index 507537391ed7eae8627ef4c1c52cfcfc5ae2ba69..48f6070ea694c6f3beb255247d07930595553063 100644
--- a/app/services/keys/create_service.rb
+++ b/app/services/keys/create_service.rb
@@ -9,6 +9,7 @@ def initialize(current_user, params = {})
       @params = params
       @ip_address = @params.delete(:ip_address)
       @user = params.delete(:user) || current_user
+      params[:organization] ||= user.organization
     end
 
     def execute
diff --git a/db/docs/keys.yml b/db/docs/keys.yml
index 51e2e53b67a308dd7aa32c7994dcf4214df2f725..4f5801542d58d29cda0b9bcd4630459cf4c1b733 100644
--- a/db/docs/keys.yml
+++ b/db/docs/keys.yml
@@ -13,4 +13,5 @@ introduced_by_url: https://gitlab.com/gitlab-org/gitlab/-/commit/9ba122486766584
 milestone: "<6.0"
 gitlab_schema: gitlab_main_org
 table_size: medium
-sharding_key_issue_url: https://gitlab.com/gitlab-org/gitlab/-/issues/553463
+sharding_key:
+  organization_id: organizations
diff --git a/db/migrate/20250911082754_add_organization_id_to_keys.rb b/db/migrate/20250911082754_add_organization_id_to_keys.rb
new file mode 100644
index 0000000000000000000000000000000000000000..e8a7f43e0ced7c2e8c93075ca76f74683512fdd0
--- /dev/null
+++ b/db/migrate/20250911082754_add_organization_id_to_keys.rb
@@ -0,0 +1,22 @@
+# frozen_string_literal: true
+
+class AddOrganizationIdToKeys < Gitlab::Database::Migration[2.3]
+  disable_ddl_transaction!
+
+  milestone '18.5'
+
+  def up
+    with_lock_retries do
+      add_column :keys, :organization_id, :bigint, default: 1, null: false
+    end
+
+    add_concurrent_index :keys, :organization_id
+    add_concurrent_foreign_key :keys, :organizations, column: :organization_id, on_delete: :cascade
+  end
+
+  def down
+    with_lock_retries do
+      remove_column :keys, :organization_id
+    end
+  end
+end
diff --git a/db/schema_migrations/20250911082754 b/db/schema_migrations/20250911082754
new file mode 100644
index 0000000000000000000000000000000000000000..2d44bc67993fc6604c746b670ffe0ffe8c538936
--- /dev/null
+++ b/db/schema_migrations/20250911082754
@@ -0,0 +1 @@
+bce6acecf5d09ad1d55acabcb906fe3fd48ad51af31a22336fdab1059cbd1aab
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 7c6f11ac89b52d65fd7f15f82484deb30b2c97fd..8206d9ec0f059c2ad5028a8fe88487e8b80b8bc6 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -18180,7 +18180,8 @@ CREATE TABLE keys (
     expires_at timestamp with time zone,
     expiry_notification_delivered_at timestamp with time zone,
     before_expiry_notification_delivered_at timestamp with time zone,
-    usage_type smallint DEFAULT 0 NOT NULL
+    usage_type smallint DEFAULT 0 NOT NULL,
+    organization_id bigint DEFAULT 1 NOT NULL
 );
 
 CREATE SEQUENCE keys_id_seq
@@ -39039,6 +39040,8 @@ CREATE INDEX index_keys_on_id_and_ldap_key_type ON keys USING btree (id) WHERE (
 
 CREATE INDEX index_keys_on_last_used_at ON keys USING btree (last_used_at DESC NULLS LAST);
 
+CREATE INDEX index_keys_on_organization_id ON keys USING btree (organization_id);
+
 CREATE INDEX index_keys_on_user_id ON keys USING btree (user_id);
 
 CREATE UNIQUE INDEX index_kubernetes_namespaces_on_cluster_project_environment_id ON clusters_kubernetes_namespaces USING btree (cluster_id, project_id, environment_id);
@@ -46302,6 +46305,9 @@ ALTER TABLE ONLY bulk_import_exports
 ALTER TABLE ONLY ml_model_versions
     ADD CONSTRAINT fk_39f8aa0b8a FOREIGN KEY (package_id) REFERENCES packages_packages(id) ON DELETE SET NULL;
 
+ALTER TABLE ONLY keys
+    ADD CONSTRAINT fk_3a0e3d4776 FOREIGN KEY (organization_id) REFERENCES organizations(id) ON DELETE CASCADE;
+
 ALTER TABLE p_ci_builds
     ADD CONSTRAINT fk_3a9eaa254d_p FOREIGN KEY (partition_id, stage_id) REFERENCES p_ci_stages(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE;
 
diff --git a/ee/lib/ee/gitlab/auth/ldap/access.rb b/ee/lib/ee/gitlab/auth/ldap/access.rb
index 670808eb27be375b7fe1dd34e92a41922e40e066..58a02a2e0d37c8ab89ef900d72544ea1dd440028 100644
--- a/ee/lib/ee/gitlab/auth/ldap/access.rb
+++ b/ee/lib/ee/gitlab/auth/ldap/access.rb
@@ -46,6 +46,7 @@ def add_new_ssh_keys
               ::Gitlab::AppLogger.info "#{self.class.name}: adding LDAP SSH key #{key.inspect} to #{user.name} (#{user.id})"
               new_key = ::LDAPKey.new(title: "LDAP - #{ldap_config.sync_ssh_keys}", key: key)
               new_key.user = user
+              new_key.organization = user.organization
 
               unless new_key.save
                 ::Gitlab::AppLogger.error "#{self.class.name}: failed to add LDAP SSH key #{key.inspect} to #{user.name} (#{user.id})\n"\
diff --git a/ee/spec/lib/gitlab/auth/ldap/access_spec.rb b/ee/spec/lib/gitlab/auth/ldap/access_spec.rb
index ca7f98f0fe8a198f818f10e7a91541684cf5df6f..37f85d78664ddd1b1967d9ca2564030ea5887f1e 100644
--- a/ee/spec/lib/gitlab/auth/ldap/access_spec.rb
+++ b/ee/spec/lib/gitlab/auth/ldap/access_spec.rb
@@ -411,7 +411,7 @@
 
       context 'user has at least one LDAPKey' do
         before do
-          user.keys.ldap.create! key: ssh_key, title: 'to be removed'
+          user.keys.ldap.create! key: ssh_key, title: 'to be removed', organization: user.organization
         end
 
         it 'removes a SSH key if it is no longer in LDAP' do
diff --git a/lib/api/deploy_keys.rb b/lib/api/deploy_keys.rb
index 29a2014d653356be7c627e7f0f45b37ff92ed5d7..4033853050c953316df57d6cdf62b4ee2adeaa56 100644
--- a/lib/api/deploy_keys.rb
+++ b/lib/api/deploy_keys.rb
@@ -159,7 +159,7 @@ def find_by_deploy_key(project, key_id)
         end
 
         # Create a new deploy key
-        deploy_key_attributes = declared_params.except(:can_push).merge(user: current_user)
+        deploy_key_attributes = declared_params.except(:can_push).merge(user: current_user, organization: current_user.organization)
         deploy_key_project = add_deploy_keys_project(user_project, deploy_key_attributes: deploy_key_attributes, can_push: !!params[:can_push])
 
         if deploy_key_project.valid?
diff --git a/spec/controllers/projects/deploy_keys_controller_spec.rb b/spec/controllers/projects/deploy_keys_controller_spec.rb
index b1021c3e689071e50ecaec9fda8a0fc37dce0136..a1398c98afed999353e1d23c154a5ecd809b5d2b 100644
--- a/spec/controllers/projects/deploy_keys_controller_spec.rb
+++ b/spec/controllers/projects/deploy_keys_controller_spec.rb
@@ -138,6 +138,13 @@ def create_params(title = 'my-key')
       expect(response).to redirect_to(project_settings_repository_path(project, anchor: 'js-deploy-keys-settings'))
     end
 
+    it 'creates a deploy key with the project organization_id' do
+      post :create, params: create_params
+
+      created_key = project.deploy_keys.last
+      expect(created_key.organization_id).to eq(project.organization_id)
+    end
+
     it 'redirects to project settings with the correct anchor' do
       post :create, params: create_params
 
@@ -322,6 +329,10 @@ def create_params(title = 'my-key')
     let(:extra_params) { {} }
     let(:project) { create(:project) }
 
+    before do
+      stub_current_organization(project.organization)
+    end
+
     subject do
       put :update, params: extra_params.reverse_merge(
         id: deploy_key.id, namespace_id: project.namespace, project_id: project
@@ -334,7 +345,7 @@ def deploy_key_params(title, can_push)
     end
 
     context 'public deploy key' do
-      let(:deploy_key) { create(:deploy_key, public: true) }
+      let(:deploy_key) { create(:deploy_key, public: true, organization: create(:common_organization)) }
       let!(:deploy_keys_project) do
         create(:deploy_keys_project, project: project, deploy_key: deploy_key)
       end
@@ -438,7 +449,7 @@ def deploy_key_params(title, can_push)
     end
 
     context 'private deploy key' do
-      let_it_be(:deploy_key) { create(:deploy_key) }
+      let_it_be(:deploy_key) { create(:deploy_key, organization: create(:common_organization)) }
       let_it_be(:extra_params) { deploy_key_params('updated title', '1') }
 
       context 'when attached to one project' do
diff --git a/spec/controllers/user_settings/ssh_keys_controller_spec.rb b/spec/controllers/user_settings/ssh_keys_controller_spec.rb
index 1d8752ff522e44f3b8d799d6942eb11ffd7d42a4..0ab5791eea5a7032cb42f3a7f965eeabc5418405 100644
--- a/spec/controllers/user_settings/ssh_keys_controller_spec.rb
+++ b/spec/controllers/user_settings/ssh_keys_controller_spec.rb
@@ -4,10 +4,12 @@
 
 RSpec.describe UserSettings::SshKeysController, feature_category: :user_profile do
   let(:user) { create(:user) }
+  let(:organization) { create(:organization) }
 
   describe 'POST #create' do
     before do
       sign_in(user)
+      stub_current_organization(organization)
     end
 
     it 'creates a new key' do
@@ -24,6 +26,13 @@
       expect(key.usage_type).to eq('signing')
     end
 
+    it 'creates a key with the current organization_id' do
+      post :create, params: { key: build(:key).attributes }
+
+      key = Key.last
+      expect(key.organization_id).to eq(organization.id)
+    end
+
     context 'with FIPS mode', :fips_mode do
       it 'creates a new key without MD5 fingerprint' do
         expires_at = 3.days.from_now
diff --git a/spec/factories/keys.rb b/spec/factories/keys.rb
index d407f2f5a5497eebdb240d30db8a474909533f40..6b33dfa65400ed9193a92fdd7667080caeb527f0 100644
--- a/spec/factories/keys.rb
+++ b/spec/factories/keys.rb
@@ -3,6 +3,7 @@
 FactoryBot.define do
   factory :key do
     sequence(:title) { |n| "title #{n}" }
+    organization
     key do
       # Larger keys take longer to generate, and since this factory gets called frequently,
       # let's only create the smallest one we need.
diff --git a/spec/features/projects/deploy_keys_spec.rb b/spec/features/projects/deploy_keys_spec.rb
index 219e47e3f0ef039085960eae253b918f7bdbce66..cc10b654756dc18ca3b784bbbded081bb77958a2 100644
--- a/spec/features/projects/deploy_keys_spec.rb
+++ b/spec/features/projects/deploy_keys_spec.rb
@@ -5,10 +5,11 @@
 RSpec.describe 'Project deploy keys', :js, feature_category: :groups_and_projects do
   let_it_be(:user) { create(:user) }
   let_it_be(:project) { create(:project_empty_repo) }
-  let_it_be(:deploy_keys_project) { create(:deploy_keys_project, project: project) }
-  let_it_be(:deploy_key) { deploy_keys_project.deploy_key }
+  let_it_be(:deploy_key) { create(:deploy_key, organization: user.organization) }
+  let_it_be(:deploy_keys_project) { create(:deploy_keys_project, project: project, deploy_key: deploy_key) }
 
   before do
+    stub_current_organization(user.organization)
     project.add_maintainer(user)
     sign_in(user)
   end
diff --git a/spec/lib/gitlab/database/sharding_key_spec.rb b/spec/lib/gitlab/database/sharding_key_spec.rb
index 19c67dc5276da861e716cc3567b29ec90590b4e5..ac3e6257d96b42c4c8b9457a7118557b9392f01a 100644
--- a/spec/lib/gitlab/database/sharding_key_spec.rb
+++ b/spec/lib/gitlab/database/sharding_key_spec.rb
@@ -306,7 +306,8 @@
       "abuse_report_events" => "https://gitlab.com/gitlab-org/gitlab/-/issues/553429",
       "abuse_events" => "https://gitlab.com/gitlab-org/gitlab/-/issues/553427",
       "abuse_report_assignees" => "https://gitlab.com/gitlab-org/gitlab/-/issues/553428",
-      "notes" => "https://gitlab.com/gitlab-org/gitlab/-/issues/569521"
+      "notes" => "https://gitlab.com/gitlab-org/gitlab/-/issues/569521",
+      "keys" => "https://gitlab.com/gitlab-org/gitlab/-/issues/569598"
     }
     has_lfk = ->(lfks) { lfks.any? { |k| k.options[:column] == 'organization_id' && k.to_table == 'organizations' } }
 
diff --git a/spec/requests/api/deploy_keys_spec.rb b/spec/requests/api/deploy_keys_spec.rb
index 45d2d54f0702abe0a9eeac4757035ae9735817d5..ef319aca465be4537c3b5c29854fd88d9653a650 100644
--- a/spec/requests/api/deploy_keys_spec.rb
+++ b/spec/requests/api/deploy_keys_spec.rb
@@ -6,9 +6,10 @@
   let_it_be(:user)        { create(:user) }
   let_it_be(:maintainer)  { create(:user) }
   let_it_be(:admin)       { create(:admin) }
-  let_it_be(:project)     { create(:project, creator_id: user.id) }
-  let_it_be(:project2)    { create(:project, creator_id: user.id) }
-  let_it_be(:project3)    { create(:project, creator_id: user.id) }
+  let_it_be(:organization) { create(:common_organization) }
+  let_it_be(:project)     { create(:project, creator_id: user.id, organization: organization) }
+  let_it_be(:project2)    { create(:project, creator_id: user.id, organization: organization) }
+  let_it_be(:project3)    { create(:project, creator_id: user.id, organization: organization) }
   let_it_be(:deploy_key) { create(:deploy_key, public: true) }
   let_it_be(:deploy_key_private) { create(:deploy_key, public: false) }
   let_it_be(:path) { '/deploy_keys' }
@@ -268,7 +269,6 @@ def perform_request
       expect do
         post api(project_path, admin, admin_mode: true), params: key_attrs
       end.to change { project.deploy_keys.count }.by(1)
-
       new_key = project.deploy_keys.last
       expect(new_key.key).to eq(key_attrs[:key])
       expect(new_key.user).to eq(admin)
diff --git a/spec/support/helpers/auth/dpop_token_helper.rb b/spec/support/helpers/auth/dpop_token_helper.rb
index 6065de46ca61de00cdcca20cac7dbe6a84b18f3b..5209261b0518fdd6ea499e4ba6ad9c796f54c789 100644
--- a/spec/support/helpers/auth/dpop_token_helper.rb
+++ b/spec/support/helpers/auth/dpop_token_helper.rb
@@ -63,7 +63,7 @@ def generate_dpop_proof_for( # rubocop:disable Metrics/ParameterLists -- all par
         "\ny1Y0tD9WVuVwFMEfkENQzOEJxVHwQpsxBRQ5snustS/HmrF5SIZyeg==" \
         "\n-----END RSA PRIVATE KEY-----"
 
-      key = user.keys.create!(title: "Sample key #{user.id}", key: ssh_public_key)
+      key = user.keys.create!(title: "Sample key #{user.id}", key: ssh_public_key, organization: user.organization)
       fingerprint ||= create_fingerprint(key.key)
       openssl_private_key = OpenSSL::PKey::RSA.new(ssh_private_key)